[Tutor] Recursion and List Comprehensions

[Carroll, Barry]

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.  

 

Here is my first try, the brute force method:

 

>>>>def permute1 (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

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

>>>>            # First isolate the char that goes in the first spot

>>>>            firstChar=word[pos]

>>>>            # Then assemble the rest of the word

>>>>            restWord=word[0:pos]+word[pos+1:len(word)]

>>>>            # Get the permutations of the rest of the word 

>>>>            restList=permute1(restWord)

>>>>            # Now, tack the first char onto each word in the list

>>>>            for item in restList:

>>>>                newWord=firstChar+item

>>>>                # and add it to the output

>>>>                retList.append(newWord)

>>>>    return retList

 

My second version combines statements to remove intermediate variables:  

 

>>>>def permute2 (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

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

>>>>            # Get the permutations of the rest of the word 

>>>>            permuteList=permute2(word[0:pos]+word[pos+1:len(word)])

>>>>            # Now, tack the first char onto each word in the list

>>>>            # and add it to the output

>>>>            for item in permuteList:

>>>>                retList.append(word[pos]+item)

>>>>    return retList

 

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.   

 

Thanks in advance for your help.  I'm learning a lot by following this list.

 

Barry

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20051028/f271ce1d/attachment.html