[Tutor] Recursion and List Comprehensions

Alan Gauld alan.gauld at freenet.co.uk
Sat Oct 29 00:00:51 CEST 2005

>>>>>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! :-)


Alan G
Author of the learn to program web tutor

More information about the Tutor mailing list