在Python中生成唯一的排列

我在尋找列表x = [「$ 5」，「$ 10」，「$ 10」，「TAX」，「$ 5」，「20％」，「BOGO 」，‘BOGO’，‘稅收’在9在Python中生成唯一的排列

組目前有什麼我做的

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

然而，這需要太長時間運行，我想知道，如果有人能夠給我更有效率的解決方案。

來源

2013-03-23 Ishidon

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

來源

2013-03-23 21:33:05 DSM

謝謝你的幫助，這完美的工作！ – Ishidon 2013-03-23 21:44:04

運行花費很長時間的原因是，當您將元素添加到列表中時，每次查找都需要更長的時間，因爲它必須搜索（平均）一半的列表。更好的方法是使用字典：

combos = {}

和：

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

這利用的hash maps查找性能。

如果您只是在進行成員資格測試，請按建議的DSM使用集合。

來源

2013-03-23 21:32:37

這比使用set（）更好嗎？ – krlmlr 2013-03-23 21:33:02

不，一套更好，因爲它更具可讀性。去DSM的答案。 – 2013-03-23 21:34:43

有關使用快速集結構的建議是好的，但你得到最好的結果，如果你不產生你不首先需要的項目。讓我們做的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作爲反例。

來源

2013-03-23 21:44:17 krlmlr

在Python中生成唯一的排列

回答

相關問題