在Python中生成唯一排列

Question

我正在寻找列表x的唯一排列，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

然而，这个运行时间太长了，我想知道是否有人能给我一个更高效的解决方案。

- Ishidon

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

- DSM

Answer 2

关于使用快速集合结构的建议很好，但如果您一开始就不生成不需要的项目，则可以获得最佳结果。让我们稍微改变对 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进行反例测试。

- krlmlr

Answer 3

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

combos = {}

并且：

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

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

---

如果你只是进行会员测试，就像DSM建议的那样使用集合。

- Martin Törnwall

---

这比使用 set() 更好吗？ - krlmlr

不，从可读性的角度来看，集合更好。采用DSM的答案。 - Martin Törnwall