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.

6 comments

James Reeves 15 years, 5 months ago  # | flag

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) 15 years, 5 months ago  # | flag

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 15 years, 5 months ago  # | flag

Why not just wrap it in set()?

Wensheng Wang (author) 15 years, 5 months ago  # | flag

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

Christopher Dunn 15 years, 5 months ago  # | flag

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 15 years, 5 months ago  # | flag

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)
Python recipes (4591)
Wensheng Wang's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks