[Tutor] permutations using list comprehensions

[Logesh Pillay]

Dear list
I was really impressed by this version of quicksort:-
def qsort (t):
   if len (t) == 0:
   return []
   else:
   return qsort([x for x in t[1:] if x = t[0]]) + [t[0]] + 
qsort([x for x in t[1:] if x  t[0]])

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.

Any ideas?
Logesh
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] permutations using list comprehensions

[Karl Pflästerer]

On  1 Mai 2005, [EMAIL PROTECTED] 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
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] permutations using list comprehensions

[Danny Yoo]

 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.


Hi Logesh,

Ok, let's try this out.  Let's assume for the moment that it works for
lists of length two.  That is, let's say that we know that:

perms([2, 3]) == [[2, 3],
  [3, 2]]

will work.  I'll pretend this without even looking at the function
definition.  *grin*


With our let's pretend hat on, now let's think about what happens if we
trying doing perms() on a slightly larger example:

perms([1, 2, 3])

on the function.  We know what we expect to get, and now we're checking to
see if our function gives that to us.


We look at the function definition, and the list isn't empty, so we hit
the recursive case:

return [[x] + perms ([y for y in t if y  x]) for x in t]


This is a bit nested, but if we expand these list comprensions out, then
we get:

return [[1] + perms([2, 3]),
[2] + perms([1, 3]),
[3] + perms([1, 2])]


This looks slightly off.  From looking at this, we already notice that the
return value only has three elements, and that's probably not what we
want.  We want a list of six elements.  (3! == 6)



But let's also take a look at one of those subexpressions --- let's look
at:

[1] + perms([2, 3])

We know that perms()  returns a list of list of integers, and:

[1] + perms([2, 3])

will do something slightly funky!  We already know what we expect out of
perms([2, 3]), so let's work this out.  We'll get back:

[1] + perms([2, 3])

== [1] + [[2, 3], [3, 2]]

== [1, [2, 3], [3, 2]]


So just from a pure typing point of view, we're in a slight mess, because
we now have a mixed list of either sublists or integers.  What I think you
want to get, instead, is something like:

[[1, 2, 3],
 [1, 3, 2]]

for the value of the first subexpression.  Does this make sense so far?



 I've also tried adding and removing square brackets in various
 combinations.

Don't flail randomly.  Just adding brackets here and there will not help.
Recursive functions demand more respect than that.  *grin*


If you have more questions, please feel free to ask.

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor