I saw a lot of implementations that doesn't work on list with repeated items. For example: [3,3,"hello","hello"] This recipe show such function that works on any list. (update 6/29/06) added generator version permu2(xs).
Python, 39 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | def permu(xs):
if xs:
r , h = [],[]
for x in xs:
if x not in h:
ts = xs[:]; ts.remove(x)
for p in permu(ts):
r.append([x]+p)
h.append(x)
return r
else:
return [[]]
def permu2(xs):
if len(xs)<2: yield xs
else:
h = []
for x in xs:
h.append(x)
if x in h[:-1]: continue
ts = xs[:]; ts.remove(x)
for ps in permu2(ts):
yield [x]+ps
print permu([1,2,3])
print
print list(permu2([4,5,6,6]))
print
print permu(['a',[1,2],'a',[1,2]])
----------- we get --------------------
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[4, 5, 6, 6], [4, 6, 5, 6], [4, 6, 6, 5], [5, 4, 6, 6], [5, 6, 4, 6], [5, 6, 6, 4],
[6, 4, 5, 6], [6, 4, 6, 5], [6, 5, 4, 6], [6, 5, 6, 4], [6, 6, 4, 5], [6, 6, 5, 4]]
[['a', [1, 2], 'a', [1, 2]], ['a', [1, 2], [1, 2], 'a'], ['a', 'a', [1, 2], [1, 2]],
[[1,2], 'a', 'a', [1, 2]], [[1, 2], 'a', [1, 2], 'a'], [[1, 2], [1, 2], 'a', 'a']]
|
list h hold items that already processed. ts is a temporary list that is the list without the current item.
Tags: algorithms
One can make a somewhat shorter version via a generator function. This has the added advantage of being somewhat more memory efficient in situations where it is not required to contain all the permutations in memory simultaneously.
even shorter, but doesn't work. def permu(xs):
if xs: return [ [xs[i]]+p for i in range(len(xs)) for p in permu(xs[:i]+xs[i+1:])]
else: return [[]]
But this, just like your and many others I found on the net, return repeated items, like two [4,5,6,6].
Permutation should not have repeated item, that's the main reason I wrote this recipe.
Why not just wrap it in set()?
because set doesn't work if item is list or dict. try set([[]]) or set([{}]).
Recursion limit. Interesting, but it is possible to hit the recursion limit (usually 1000).
Here is a way to produce successive permutations. It does handle duplicates, and it could easily be made into a generator. (Swap lt with gt in value comparisons to compute prev.)
</pre>
HTML problems. The less-than and greater-than chars in my solution seem to cause HTML problems, despite using pre tags. Very annoying. I'll post a separate recipe.