|
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 |
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
