#!/usr/bin/python2.5
def permute(li):
"""Generate all permutations of a sequence
>>> for i in permute([1,2,3]): print i
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)"""
return ((i,)+j for i in li for j in (permute([k for k in li if k is not i])
if len(li) > 1 else [()] ) )
import doctest
doctest.testmod(verbose=True)
Refactorings
No refactoring yet !
Auron
October 22, 2008, October 22, 2008 08:20, permalink
Your code works great but addresses a different problem than this one (http://refactormycode.com/codes/523-permutation-of-values), which is really not a permutation (it was my fault).
I like your one-line solution, although I find it difficult to understand :)
William Bowers
October 30, 2008, October 30, 2008 07:29, permalink
First off let me say your solution is already an elegant one. I only made one change: I shortened your list comprehension (or I guess in this case, generator comprehension) by making use of a sort of ternary operator hack; if you don't already know, placing a boolean value as an index for a tuple will evaluate to 1 if True and 0 if False. Thus ("foo", "bar")[False] evaluates to "foo" and ("foo", "bar")[True] evaluates to "bar".
Nice work though :) took me a minute to understand the logic behind this one.
#!/usr/bin/python2.5
def permute(li):
return ((i,)+j for i in li for j in (([()], permute([k for k in li if k is not i]))[len(li) > 1]))
for i in permute([1, 2, 3]):
print i
Leif Ryge
October 30, 2008, October 30, 2008 20:23, permalink
Thanks! I was actually unaware that booleans could be used as getitem keys, which is a very useful trick. I wonder why I've seen this ugly idiom A in wide use instead of the much more elegant B:
idiom_A = lambda x,y,z: (x and [y] or [z])[0] idiom_B = lambda x,y,z: (z, y)[x] idiom_C = lambda x,y,z: y if x else z # introduced in Python 2.5
Leif Ryge
October 31, 2008, October 31, 2008 06:55, permalink
Answering my own question: the caveat to idiom_B is that it isn't short-circuiting. So, if instead of z and y we had z() and y() then evaluating the expression causes BOTH functions to be called (regardless of the value of x) in idiom_B, while in A and C only the desired function is called.
William Bowers
October 31, 2008, October 31, 2008 20:41, permalink
That's very true. In this case it would be better to go with A, as you probably don't want that last call to permute() to go off. I prefer B in case where it doesn't really matter, like when Z and Y are both strings or numbers, or when both Z and Y need to go off anyway. Either way works, A is faster :)
I suspect there is a better way to deal with the end of the sequence.