All permutations of a list

[Alex Martelli]

"Richard van de Stadt" <stadt at cs.utwente.nl> wrote in message
news:39F8A95B.F34978F8 at cs.utwente.nl...
    [snip]
> Rainer Deyke wrote:
> > 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:])]
>
> My collegue found another Miranda/Amanda solution, which looks
> similar (or is it _the_ equivalent?)
>
> perms [] = [[]]
> perms l  = [ x:p | x <- l ; p <- perms (l--[x]) ]
>
> x <- l: x walks through all values of l
> for every x, p is set to all permutations of l_without_x
> x:p means x with p appended.

I think a closer Python equivalent would be (mimicking
the Miranda variable names too):

def perms(l):
    if l == []: return [[]]
    return [ [x]+p for x in l for p in perms( remove(l,x) ) ]

except that Python has no built-in way to return a _copy_
of a list with certain alterations (except for the append
operator), so the remove function should also be supplied:

def remove(l,x):
    l=l[:]
    l.remove(x)
    return l

Rainer's solution, by iterating on indices rather than on
list-contents, manages to achieve the desired result (get a
list like l, except it's without element x, without altering
l itself) -- except it arguably does it better, since it
behaves quite well even if the input list has duplicates
(I'm not sure about the semantics of Miranda's --... what
happens if the list has more than one occurrence of x...?).

I.e., Rainer's version acts on lists-with-duplicates "just
as if" the duplicate elements were 'invisibly tagged' so
as to be distinguishable; my version gives a different
ordering if duplicates are present (since it's always the
*first* occurrence that gets removed).


An interesting variation, thinking of lists with duplicate
elements allowed, is to produce only the *distinguishable*
permutations (i.e. have a permutations-list that does NOT
have duplicates itself, though the base-list does).  I
think all it takes is adding a guard, to handle only those
elements that are their first occurrence in the list, i.e.,
for Rainer's version:

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


Alex