# [Tutor] Recursion and List Comprehensions

Carroll, Barry Barry.Carroll at psc.com
Sat Oct 29 02:48:36 CEST 2005

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

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

```