1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#!/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.
1 2 3 4 5 6 7
#!/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:
1 2 3
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.