[Tutor] A small math puzzle [recreational Python]

[Andy W]

Here's a solution, albeit a cruddy one :-)
It uses permutations, so therefore gets dreadfully slow from about 8 letters
onwards.
I knew this would happen, I just couldn't get my mind around the
mathematical approach...

Andy W.

PS. The function actually returns all the rearrangements, not the number of
them. Of course that can easily be changed...

#Code

def perm(set,n):
  """
  By Kirby Urner.
  Return all permutations of a set.  Thanks to
  Daniel Ajoy for sharing his Logo version with me.
  """

  set=listify(set)

  if len(set)==0:  return []
  elif len(set)==1:  return set
  answ = []

  for i in range(len(set)):
    base = [set[0]]
    rest = set[1:]
    answ = answ + [base + listify(i) for i in perm(rest,n-1)]
    set = [set[-1]]+set[:-1]

  return answ

def listify(obj):
  "Used in conjunction with perm()"
  if type(obj) is not type([]):
    try:
      l=list(obj)
    except:
      l=[obj]
    return l
  else: return obj

def get_rearrangements(word):
  word=word.upper()
  perms=perm([char for char in word],len(word))  #Get the permutations of
the letters
  rearrangements=perms[:] #Copy for keeping the good ones in
  for p in perms:
    ok=1
    for n in range(len(p)):
      if p[n]==word[n]: #Check whether the character is the same...
        ok=0
    if not ok:
      rearrangements.remove(p) #If it is, remove it!
  return [''.join(r) for r in rearrangements]

----- Original Message -----
From: "Danny Yoo" <dyoo@hkn.eecs.berkeley.edu>
To: <tutor@python.org>
Sent: Saturday, January 05, 2002 5:53 PM
Subject: [Tutor] A small math puzzle [recreational Python]


> Hi everyone,
>
> I ran across this puzzle while browsing the the 'alt.math.undergrad'
> newsgroup.  I thought it might make a fun programming exercise, so here's
> my paraphrase of the puzzle:
>
>
> A "rearrangement without fixed letters" of a given word is a mixup of the
> letters so that, if one were to overlap the original with the
> rearrangement, no letters should match.  For example, given the word:
>
>     'TERESA'
>
> here are a two "rearrangements without fixed letters":
>
>     ['RTESAE', 'SATREE']
>
> However, here's an example that is a rearrangement but doesn't work
> because it has a fixed letter:
>
>     'TRESAE'
>      ^
>
> In this example, the 'T' makes this rearrangement inacceptable, since
> 'TERESA' itself begins with a 'T' too.
>
>
> The puzzle is to write a program that counts all the possible
> rearrangements without fixed letters.
>
>
> Have fun!
>
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
>