在Python中生成唯一排列

3 投票

3 回答

4758 浏览

提问于 2025-04-17 20:05

我想找出这个列表中所有独特的排列组合，列表是 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

不过，这样运行起来太慢了，我在想有没有人能给我一个更有效的解决办法。

数据结构算法优化排列组合性能提升唯一排列

3 个回答

运行时间长的原因是，当你往列表里添加元素时，每次查找都需要花更多时间，因为它平均要搜索列表的一半。一个更好的方法是使用字典：

combos = {}

还有：

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

这样做利用了哈希表的查找性能。

如果你只是想检查某个元素是否在里面，按照DSM的建议，使用集合会更好。

回答于 2025-04-17 由 Python大师

分享举报

关于使用快速集合结构的建议是不错的，但如果一开始就不生成那些不需要的项目，效果会更好。我们来用一种稍微不同的方式表示 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 来做个反例。

回答于 2025-04-17 由 Python大师

分享举报

在代码中，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

回答于 2025-04-17 由 Python大师

分享举报

在Python中生成唯一排列

3 个回答

撰写回答