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.
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
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.
The reason it takes long to run is that as you append elements to the list, each lookup takes longer because it has to search (on average) half the list. A better approach is to use a dictionary:
combos = {}
And:
if i not in combos:
combos[i] = None # Just to put something there unless you need to store a value
This exploits the lookup performance of hash maps.
If you are just doing membership testing, use sets as DSM suggested.
