Создание уникальных перестановок в Python

Question

Я ищу, чтобы найти уникальные перестановки в списке, x = ["$ 5", "$ 10", "$ 10", "TAX", "$ 5", "20%", "BOGO »,„BOGO“,„НАЛОГ“] в группах 9

Что я сейчас делаю это

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 

Однако, это занимает слишком много времени, чтобы работать и мне было интересно, если кто-то может дать мне более эффективное решение .

Answer 1

if i not in combos: займет много времени, поскольку тестирование членства в списке (в худшем случае) O (N) - оно должно сканировать каждый элемент. Вы можете использовать вместо set:

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

Причина, по которой требуется много времени, заключается в том, что при добавлении элементов в список каждый поиск занимает больше времени, поскольку он должен искать (в среднем) половину списка. Лучший подход заключается в использовании словаря:

combos = {} 

И:

if i not in combos: 
    combos[i] = None # Just to put something there unless you need to store a value 

Это эксплуатирующий производительность подстановок из hash maps.

Если вы только что проводите тестирование членства, используйте наборы, как предлагалось DSM.

Answer 3

Предложения об использовании быстрого набора структуры хороши, но вы получите лучшие результаты, если вы не генерировать элементы, которые не нужны в первую очередь. Давайте немного другое представление x:

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

Тогда следующая функция должна получить вам неповторяющиеся перестановки:

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 

Это рекурсия. На каждом шаге мы выбираем пункт и количество повторений. Плюс мы избегаем выбора одного и того же элемента на следующем уровне рекурсии.

Для вашего экземпляра проблемы этот код медленнее, чем подход с set. Однако попробуйте с x = [1] * 30 для контрпримера.