Carroll, Barry wrote:
> 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.
<snip>
> 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.
There's nothing magic about writing a list comprehension - they're just
an inside-out way of writing a for-loop :).
newlist = []
for item in mylist:
newlist.append(item * 2)
becomes (imagine this as an animation with bits of code from above
floating down to fill in the blanks :)):
newlist = [ ]
newlist = [ for item in mylist]
newlist = [item * 2 for item in mylist]
In your case, you could start with your permute2 implementation and turn
it inside out to get a list comprehension:
for item in permuteList:
retList.append(word[pos] + item)
would become according to the example above:
retList = [word[pos] + item for item in permuteList]
Testing this shows that it tends to cut off a bunch of combinations,
because retList is overwritten in every iteration of "for pos in range".
Let's fix that by extending the list instead:
retList.extend([word[pos] + item for item in permuteList])
That works. Now we replace 'permuteList' with its definition a few lines
above:
retList.extend([word[pos] + item
for item in permute2(word[0:pos]+word[pos+1:len(word)])])
Getting ugly now. Let's see what's missing: word is an argument, item
comes from the "for item in ...", but pos still needs to be defined. We
get that by wrapping the "for pos in range" loop around this list
comprehension:
for pos in range(len(word)):
dosomething(pos)
becomes:
[dosomething(pos) for pos in range(len(word))]
Where dosomething(pos) is our earlier list comprehension. Let's fill it in:
[ retList.extend(
[ word[pos] + item
for item in permute2(word[0:pos]+word[pos+1:len(word)]) ] )
for pos in range(len(word))]
The net result:
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.extend(
[ word[pos] + item
for item in permute3(word[0:pos]+word[pos+1:len(word)]) ] )
for pos in range(len(word))]
return retList
4 lines of perfectly readable code have become 4 lines of perfectly
unreadable list comprehension. Any reader interested in understanding
this will have to perform the exact opposite set of operations to go
back to the original code.
--
Yours,
Andrei
=====
Mail address in header catches spam. Real contact info:
''.join([''.join(s) for s in zip(
"[EMAIL PROTECTED] pmfe!Pes ontuei ulcpss edtels,s hr' one oC.",
"rjc5wndon.Sa-re laed o s npbi ot.Ira h it oteesn edt C")])
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
