ActiveState Code

Recipe 496819: A recursive function to get permutation of a list

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 
 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']]

Discussion

list h hold items that already processed. ts is a temporary list that is the list without the current item.

Comments

  1. 1. At 3:28 a.m. on 27 jun 2006, James Reeves said:

    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]))
  2. 2. At 9:17 a.m. on 27 jun 2006, Wensheng Wang (the author) said:

    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.

  3. 3. At 3 a.m. on 28 jun 2006, James Reeves said:

    Why not just wrap it in set()?

  4. 4. At 9:55 a.m. on 28 jun 2006, Wensheng Wang (the author) said:

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

  5. 5. At 2:30 p.m. on 6 jul 2006, Christopher Dunn said:

    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>

  6. 6. At 2:31 p.m. on 6 jul 2006, Christopher Dunn said:

    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.

Sign in to comment