在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中生成唯一的排列

回答

相关问题