Python non-unique permutations processing

Question

I have a problem that I'm trying to solve with itertools product. It is a permutations problem, but the values are not unique, example:

list = [1,1,2,2,3,3]
#result should be
[1,2,1,2,3,3], [2,2,1,1,3,3], .....

I tried using set(itertools.permutations(list))which is the straightforward answer, but the processing time for it is too much for different values and long lists. I tried also x = itertools.product(set(list),repeat=len(list)) then cleaning out x from the items that don't fulfill the original list value counts (i.e. the generated lists must have two 1s, two 2s, and two 3s), this solution is more quick but this answer throws MemoryError with large numbers because it tries storing the output in the memory then doing the processing on it.

I tried also looping through the product result (i.e for i in itertools.product(set(list),repeat=len(list)) and selecting which iterations to store in and which iterations to throw away) and this solution solves the memory error problem, but is almost as slow as the first one, in which the code could run for hours.

Does anyone have any suggestions how would be a more efficient way to solve this problem?

These are called multisets and there is a tool already out there for this very purpose from `sympy`. — Joseph Wood, Dec 14 '18 at 13:11

score 0 · Answer 1 · answered Dec 13 '18 at 16:48

Here's how I might approach the problem. Take each unique starting value and then all the unique combinations from the values with the starting value removed. It avoids generating any duplicates but only stores the unique values used in each position so worst case an n element list is n-squared in memory.

import itertools

def unique_permutations(values):
    if not values:
        yield []
        return
    seen = set()
    for idx, first in enumerate(values):
        if first in seen:
            continue
        seen.add(first)

        rest = values[:idx] + values[idx+1:]
        for perm in unique_permutations(rest):
            yield [first] + perm

values = [1, 1, 2, 2, 3, 3]
for perm in unique_permutations(values):
    print(perm)

Output:

[1, 1, 2, 2, 3, 3]
[1, 1, 2, 3, 2, 3]
[1, 1, 2, 3, 3, 2]
[1, 1, 3, 2, 2, 3]
[1, 1, 3, 2, 3, 2]
[1, 1, 3, 3, 2, 2]
[1, 2, 1, 2, 3, 3]
[1, 2, 1, 3, 2, 3]
[1, 2, 1, 3, 3, 2]
[1, 2, 2, 1, 3, 3]
[1, 2, 2, 3, 1, 3]
[1, 2, 2, 3, 3, 1]
[1, 2, 3, 1, 2, 3]
[1, 2, 3, 1, 3, 2]
[1, 2, 3, 2, 1, 3]
[1, 2, 3, 2, 3, 1]
[1, 2, 3, 3, 1, 2]
[1, 2, 3, 3, 2, 1]
[1, 3, 1, 2, 2, 3]
[1, 3, 1, 2, 3, 2]
[1, 3, 1, 3, 2, 2]
[1, 3, 2, 1, 2, 3]
[1, 3, 2, 1, 3, 2]
[1, 3, 2, 2, 1, 3]
[1, 3, 2, 2, 3, 1]
[1, 3, 2, 3, 1, 2]
[1, 3, 2, 3, 2, 1]
[1, 3, 3, 1, 2, 2]
[1, 3, 3, 2, 1, 2]
[1, 3, 3, 2, 2, 1]
[2, 1, 1, 2, 3, 3]
[2, 1, 1, 3, 2, 3]
[2, 1, 1, 3, 3, 2]
[2, 1, 2, 1, 3, 3]
[2, 1, 2, 3, 1, 3]
[2, 1, 2, 3, 3, 1]
[2, 1, 3, 1, 2, 3]
[2, 1, 3, 1, 3, 2]
[2, 1, 3, 2, 1, 3]
[2, 1, 3, 2, 3, 1]
[2, 1, 3, 3, 1, 2]
[2, 1, 3, 3, 2, 1]
[2, 2, 1, 1, 3, 3]
[2, 2, 1, 3, 1, 3]
[2, 2, 1, 3, 3, 1]
[2, 2, 3, 1, 1, 3]
[2, 2, 3, 1, 3, 1]
[2, 2, 3, 3, 1, 1]
[2, 3, 1, 1, 2, 3]
[2, 3, 1, 1, 3, 2]
[2, 3, 1, 2, 1, 3]
[2, 3, 1, 2, 3, 1]
[2, 3, 1, 3, 1, 2]
[2, 3, 1, 3, 2, 1]
[2, 3, 2, 1, 1, 3]
[2, 3, 2, 1, 3, 1]
[2, 3, 2, 3, 1, 1]
[2, 3, 3, 1, 1, 2]
[2, 3, 3, 1, 2, 1]
[2, 3, 3, 2, 1, 1]
[3, 1, 1, 2, 2, 3]
[3, 1, 1, 2, 3, 2]
[3, 1, 1, 3, 2, 2]
[3, 1, 2, 1, 2, 3]
[3, 1, 2, 1, 3, 2]
[3, 1, 2, 2, 1, 3]
[3, 1, 2, 2, 3, 1]
[3, 1, 2, 3, 1, 2]
[3, 1, 2, 3, 2, 1]
[3, 1, 3, 1, 2, 2]
[3, 1, 3, 2, 1, 2]
[3, 1, 3, 2, 2, 1]
[3, 2, 1, 1, 2, 3]
[3, 2, 1, 1, 3, 2]
[3, 2, 1, 2, 1, 3]
[3, 2, 1, 2, 3, 1]
[3, 2, 1, 3, 1, 2]
[3, 2, 1, 3, 2, 1]
[3, 2, 2, 1, 1, 3]
[3, 2, 2, 1, 3, 1]
[3, 2, 2, 3, 1, 1]
[3, 2, 3, 1, 1, 2]
[3, 2, 3, 1, 2, 1]
[3, 2, 3, 2, 1, 1]
[3, 3, 1, 1, 2, 2]
[3, 3, 1, 2, 1, 2]
[3, 3, 1, 2, 2, 1]
[3, 3, 2, 1, 1, 2]
[3, 3, 2, 1, 2, 1]
[3, 3, 2, 2, 1, 1]

Python non-unique permutations processing

1 Answers1