All permutations of a list

[Rainer Deyke]

"Richard van de Stadt" <stadt at cs.utwente.nl> wrote in message
news:39F393B5.A978CC9D at cs.utwente.nl...
> Rainer Deyke wrote:
> > def ins(a, list):
> >   return [list[:i] + [a] + list[i:] for i in range(len(list) + 1)]
>
> After having seen this, my colleague came up with this two-line solution,
> a version that doesn't need an ins-part:
>
> perms [] = [[]]
> perms xs = concat [ map (x:) (perms (xs--[x])) | x <- xs ]
>
> How would that be in Python? I guess it's about time I start
> downloading v2.0.

If 'xs--[x]' means what I think it means, things become awkward because
Python does not define this operation as an operator.  I suppose one could
add a utility function, but I'm not entirely sure how the '--' operator is
defined.

def list_without(list, element):
  list = list[:]
  list.remove(element)
  return list

def concat(list): # Same as before
 return [e for l in list for e in l]

def perms(xs):
  if xs == []:
    return [[]]
  return concat([map(lambda tail, head=x: [head] + tail,\
    perms(list_without(xs, x))) for x in xs])

Here's my short Pythonic permutation function:

def perms(list):
  if list == []:
    return [[]]
  return [[list[i]] + p for i in range(len(list))\
    for p in perms(list[:i] + list[i+1:])]


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