Computing permutations with a recursive generator expression
#!/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)
Computing permutations with a recursive generator expression…
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 unde…
Computing permutations with a recursive generator expression…
First off let me say your solution is already an elegant one. I made a couple changes. First off you’ll notice I turn the list into a Set which removes any duplicate values (that may or may not be what you want). Secondly, I shortened your list compre…
Computing permutations with a recursive generator expression…
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 the horribly ugly idiom_A [below] in wide use instead of the much more elegant B….
Computing permutations with a recursive generator expression…
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 an…
Computing permutations with a recursive generator expression…
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 …