[Tutor] help with list permutations

Chris Fuller cfuller084 at thinkingplanet.net
Fri Jan 4 08:15:33 CET 2008


This is a good case for recursion. My solution is in two steps. A straightforward application of recursion (I was casting about semi-randomly) yields a attractive tree structure:

               root
       a                  b
 c     d     e      c     d    e
 f     f     f      f     f    f
g h   g h   g h    g h   g h  g h

It returns a list, of course, but when unpacked in two dimensions looks like a tree. Trees are often represented this way in programming.

One thing to note is that the tree structure naturally preserves the order of the lists, as required.


Here is the code:

def recursion_is_your_friend(l):
   if len(l) == 1:
      return l
   else:
      return [ (i, recursion_is_your_friend(l[1:])) for i in l[0] ]

l = recursion_is_your_friend([['a','b'],['c','d','e'],['f'],['g','h']])


The idea is that each element of the first list in the list has all the rest of the lists applied to it. Something like that. Talking about recursion isn't a skill I have much skill in. Cue groaning!

The next step is to trace all the paths from the root to the leaves. There is a wikipedia page that discusses this: http://en.wikipedia.org/wiki/Depth-first_search. Stacks would seem a natural way to do this to me. It can also be done with more recursion. I may implement something a little later, but this should get you started. Another way to look at step two is to start at the leaves and follow the (unique) path back to the root.

Cheers


More information about the Tutor mailing list