[Tutor] Recursion and List Comprehensions

[Carroll, Barry]

Alan et al:

After reading the topic you recommended I tried rewriting my permute
function as follows: 

##########
def permute3 (word):
    if len(word) == 1:
        # There is only one possible permutation
        retList=[word]
    else:
        # Return a list of all permutations using all characters
        for pos in range(len(word)):
            # Get the permutations of the rest of the word, 
            # tack the first char onto each word in the list
            # and add it to the output
            retList=[word[pos]+item for item in permute3(word[0:pos]+
word[pos+1:])]
    return retList
##########

The list comprehension looks correct to my eyes.  However, when I run the
function I always get back a one element list.  For example

>>>>>>>>>>
>>> permute.permute3('test')
['tset']
>>>>>>>>>>

By contrast my previous version returns the correct output:

>>>>>>>>>>
>>> permute.permute2('test')
['test', 'tets', 'tset', 'tste', 'ttes', 'ttse', 'etst', 'etts', 'estt',
'estt', 'etts', 'etst', 'stet', 'stte', 'sett', 'sett', 'stte', 'stet',
'ttes', 'ttse', 'tets', 'test', 'tste', 'tset']
>>>
>>>>>>>>>>

Note that permute3 returns the last element of the list returned by
permute2.  This is true in general:  permute3 always returns the last
element generated by permute2.  

I think there is a problem with the assignment (retList= ...), but the
append operator (retList+= ...) causes this error:

>>>>>>>>>>
>>> permute.permute3('tests')
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "permute.py", line 50, in permute3
    retList+=[word[pos]+item for item in
permute3(word[0:pos]+word[pos+1:len(word)])]
UnboundLocalError: local variable 'retList' referenced before assignment
>>>>>>>>>>

Ideas, anyone?  

Thanks again.  

Barry

-----Original Message-----
From: Alan Gauld [mailto:alan.gauld at freenet.co.uk] 
Sent: Friday, October 28, 2005 3:01 PM
To: Carroll, Barry; tutor at python.org
Subject: Re: [Tutor] Recursion and List Comprehensions

>>>>>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]

retlist += [ word[0] + item , item  for item in permute3(word[1:]) ]

>>>>>    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.

Take a look in the functional programming topic of my tutor for an
explanation of comprehensions. The code above is untested but
should be close I think. It tries to produce a list of each item in the
permutation list plus the same item with the first char added.
However one point to consider is whether order matters.

Take 'te' as your word
t, te, e

is what the above gives but you could argue that 'et' is also a permutation,
if so, my comprehension doesn't give that. And its quite hard to generate
(ie I can't think of an easy way! :-)

HTH,

Alan G
Author of the learn to program web tutor
http://www.freenetpages.co.uk/hp/alan.gauld