Generating Unique Permutations in Python [duplicate]

Question

I am looking to find the unique permutations of the list, x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX"] in groups of 9

What i'm currently doing is

from itertools import permutations
x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX"]
combos = []
for i in permutations(x, 9):
    if i not in combos:
        combos.append(i)
print combos

However, this takes far too long to run and I was wondering if someone could give me a more efficient solution.

Answer 1

if i not in combos: will take a long time because membership testing in a list is (worst-case) O(N) -- it has to scan through each element. You can use a set instead:

>>> from itertools import permutations
>>> x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX", "BOGO"]
>>> %time p = set(permutations(x, 9))
CPU times: user 0.88 s, sys: 0.01 s, total: 0.90 s
Wall time: 0.90 s
>>> len(p)
75600

Answer 2

The suggestions about using a fast set structure are good, but you get best results if you don't generate the items you don't need in the first place. Let's do a slightly different representation of x:

from collections import OrderedDict
x = OrderedDict([("$5", 2), ("$10", 2), ("TAX", 2), ("20%", 1), ("BOGO", 3)])

Then, the following function should get you non-repeating permutations:

from copy import copy
def permutations_unique(x, curr_list=[]):
    if not x:
        yield curr_list
        return
    last_item = None
    if curr_list:
        last_item = curr_list[-1]
    for item in x:
        if item != last_item:
            for j in range(1, x[item] + 1):
                xchild = copy(x)
                xchild[item] -= j
                if xchild[item] == 0:
                    del xchild[item]
                for y in permutations_unique(xchild, curr_list + [item] * j):
                    yield y

It's a recursion. At each step we choose the item and the number of repetitions. Plus we avoid choosing the same item at the next level of the recursion.

For your problem instance, this code is slower than the approach with a set. However, try with x = [1] * 30 for a counterexample.