[Tutor] permutations using list comprehensions

[Karl Pflästerer]

On  1 Mai 2005, logesh at iafrica.com wrote:

> I'm trying to produce something of a similar structure to generate the 
> permutations of a sequence by translating the ffg bit of Haskell:-
> perms [] = [[]]
> perms xs = [ x : ps | x <- xs , ps <- perms ( xs\\[x]) ]
>
> '\\' applies to lists & means elements of the first list excluding any 
> elements in common with the second list.
>
> The best I've been able to do is pretty obvious:-
> def perms (t):
>    if len (t) == 0:
>        return []
>    else:
>        return [[x] + perms ([y for y in t if y <> x]) for x in t]
>       
> Needless to say, it doesn't work.  It does produce a list of lists but 
> they are so horribly nested that I've no idea whether I am getting 
> close.  I've also tried adding and removing square brackets in various 
> combinations.

Just do the same as the Haskell code does:

def perms (lst):
    if lst:
        return [[x] + ps
                for x in lst
                for ps in perms([e for e in lst if e != x])]
    else:
        return [[]]


But remember that recursion in Python isn't as nice as in e.g Haskell
(sadly).



   Karl
-- 
Please do *not* send copies of replies to me.
I read the list