[Tutor] Recursion and List Comprehensions

[Andrei]

Carroll, Barry wrote:
> Greetings:
> I'm trying to improve my programming and Python skills.  To that end I 
> have implemented a word jumble program as a recursive function:  given a 
> string of arbitrary length, return a list of all permutations of the 
> string each character exactly once.  In other words:
> 
>     permute('t') = ['t'],
>     permute('te') = ['te', 'et'],
>     permute('tes') = ['tes', 'tse', 'ets', 'est', 'ste', 'set'],
>     etc. 
<snip>
> I'm told that I can collapse the logic further by using a list 
> comprehension, something like:
>> >>>def permute3 (word):
>> >>>    retList=[]
>> >>>    if len(word) == 1:
>> >>>        # There is only one possible permutation
>> >>>        retList.append(word)
>> >>>    else:
>> >>>        # Return a list of all permutations using all characters
>> >>>        retlist = [a list comprehension that calls permute3]
>> >>>    return retList
> Unfortunately, I don't understand how list comprehensions work and how 
> to implement them.  Can someone point me in the right direction, please.

There's nothing magic about writing a list comprehension - they're just 
an inside-out way of writing a for-loop :).

   newlist = []
   for item in mylist:
       newlist.append(item * 2)

becomes (imagine this as an animation with bits of code from above 
floating down to fill in the blanks :)):

   newlist = [                           ]
   newlist = [         for item in mylist]
   newlist = [item * 2 for item in mylist]


In your case, you could start with your permute2 implementation and turn 
it inside out to get a list comprehension:

   for item in permuteList:
       retList.append(word[pos] + item)

would become according to the example above:

   retList = [word[pos] + item for item in permuteList]

Testing this shows that it tends to cut off a bunch of combinations, 
because retList is overwritten in every iteration of "for pos in range". 
Let's fix that by extending the list instead:

   retList.extend([word[pos] + item for item in permuteList])

That works. Now we replace 'permuteList' with its definition a few lines 
above:

   retList.extend([word[pos] + item
     for item in permute2(word[0:pos]+word[pos+1:len(word)])])

Getting ugly now. Let's see what's missing: word is an argument, item 
comes from the "for item in ...", but pos still needs to be defined. We 
get that by wrapping the "for pos in range" loop around this list 
comprehension:

   for pos in range(len(word)):
       dosomething(pos)

becomes:

   [dosomething(pos) for pos in range(len(word))]

Where dosomething(pos) is our earlier list comprehension. Let's fill it in:

   [ retList.extend(
       [ word[pos] + item
         for item in permute2(word[0:pos]+word[pos+1:len(word)]) ] )
     for pos in range(len(word))]

The net result:

   def permute3(word):
       retList=[]
       if len(word) == 1:
           # There is only one possible permutation
           retList.append(word)
       else:
           # Return a list of all permutations using all characters
           [ retList.extend(
                 [ word[pos] + item
             for item in permute3(word[0:pos]+word[pos+1:len(word)]) ] )
             for pos in range(len(word))]
       return retList

4 lines of perfectly readable code have become 4 lines of perfectly 
unreadable list comprehension. Any reader interested in understanding 
this will have to perform the exact opposite set of operations to go 
back to the original code.



-- 
Yours,

Andrei

=====
Mail address in header catches spam. Real contact info:
''.join([''.join(s) for s in zip(
"poet at aao.l pmfe!Pes ontuei ulcpss  edtels,s hr' one oC.",
"rjc5wndon.Sa-re laed o s npbi ot.Ira h it oteesn edt C")])