Welcome, guest | Sign In | My Account | Store | Cart

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
 ``` 1 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.

James Reeves 17 years, 10 months ago

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.

``````def permu(xs):
if len(xs) &lt;= 1:
yield xs
else:
for i in range(len(xs)):
for p in permu(xs[:i] + xs[i + 1:]):
yield [xs[i]] + p

print list(permu([4,5,6,6]))
``````
Wensheng Wang (author) 17 years, 10 months ago

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.

James Reeves 17 years, 10 months ago

Why not just wrap it in set()?

Wensheng Wang (author) 17 years, 10 months ago

because set doesn't work if item is list or dict. try set([[]]) or set([{}]).

Christopher Dunn 17 years, 9 months ago

Recursion limit. Interesting, but it is possible to hit the recursion limit (usually 1000).

``````>>> permu2(range(1001)).next()
``````

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.)

``````def permute_next(values):
"""
Alter the list of values in-place to produce to the next permutation
in lexicographical order.

'values' must support slicing and ::reverse().
"""
last = len(values) - 1
a = last
while a > 0:
b = a
a -= 1
if values[a] Interesting, but it is possible to hit the recursion limit (usually 1000).

>>> permu2(range(1001)).next()

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>
def permute_next(values):
"""
Alter the list of values in-place to produce to the next permutation
in lexicographical order.

'values' must support slicing and ::reverse().
"""
last = len(values) - 1
a = last
while a > 0:
b = a
a -= 1
if values[a]
``````

</pre>

Christopher Dunn 17 years, 9 months ago

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.

 Created by Wensheng Wang on Fri, 23 Jun 2006 (PSF)

### Required Modules

• (none specified)