3

我正在寻找列表的独特排列，x = [“$5”、“$10”、“$10”、“TAX”、“$5”、“20%”、“BOGO”、“BOGO”、“TAX” "] 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

但是，这需要很长时间才能运行，我想知道是否有人可以给我一个更有效的解决方案。

4

3 回答 3

7

if i not in combos:将需要很长时间，因为列表中的成员资格测试是（最坏情况）O（N） - 它必须扫描每个元素。您可以使用 aset代替：

>>> 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-23T21:33:05.773 回答
1

关于使用快速集合结构的建议很好，但如果您不首先生成不需要的项目，您将获得最佳结果。让我们做一个稍微不同的表示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-23T21:44:17.160 回答
0

运行需要很长时间的原因是，当您将元素附加到列表时，每次查找需要更长的时间，因为它必须搜索（平均）列表的一半。更好的方法是使用字典：

combos = {}

和：

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

这利用了哈希映射的查找性能。

如果您只是进行成员资格测试，请按照 DSM 的建议使用集合。

于 2013-03-23T21:32:37.630 回答