All permutations of a list

[Rainer Deyke]

"Richard van de Stadt" <stadt at cs.utwente.nl> wrote in message
news:39F1FB22.6E9246E7 at cs.utwente.nl...
> Then a collegue of mine impressed me with a recursive program
> in the functional language Miranda/Amanda:
>
> ins a []     = [[a]]
> ins a (x:xs) = (a:x:xs) : map (x:) (ins a xs)
>
> perms []     = [[]]
> perms (x:xs) = concat (map (ins x) (perms xs))
>
> 'ins a xs' returns a list of all possible extensions of
> the list xs by inserting element a.
> 'perms xs' returns the list of all possible permutations
> of the list xs.
> 'concat' joins lists.
>
> Is such an elegant recursive solution possible in Python?

Here's a direct translation:

def ins(a, list):
  if list == []:
    return [[a]]
  return [[a] + list] + map(lambda tail, head = list[0]:\
    [head] + tail, ins(a, list[1:]))

def perms(list):
  if list == []:
    return [[]]
  return concat(map(lambda tail, head = list[0]: ins(head, tail),
    perms(list[1:])))

def concat(list):
  return [o for l in list for o in l]

This can be made more elegant by using Python idioms.  For exampe, the
function 'ins' could be rewritten like this:

def ins(a, list):
  return [list[:i] + [a] + list[i:] for i in range(len(list) + 1)]


--
Rainer Deyke (root at rainerdeyke.com)
Shareware computer games           -           http://rainerdeyke.com
"In ihren Reihen zu stehen heisst unter Feinden zu kaempfen" - Abigor