在Python中生成唯一置换

2024-06-01 00:01:52 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在寻找列表的唯一排列,x=[“5美元”、“$10”、“$10”、“$10”、“税”、“$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

然而,这需要太长的时间来运行,我想知道是否有人可以给我更多 有效的解决方案。在


Tags: infromimport列表forif时间not
3条回答

运行它需要很长时间的原因是,当您向列表添加元素时,每次查找都要花费较长的时间,因为它必须(平均)搜索列表的一半。更好的方法是使用字典:

combos = {}

以及:

^{pr2}$

这将利用hash maps的查找性能。在


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

关于使用快速集合结构的建议是很好的,但是如果你不生成一开始就不需要的项目,你会得到最好的结果。让我们对x做一个稍微不同的表示:

from collections import OrderedDict
x = OrderedDict([("$5", 2), ("$10", 2), ("TAX", 2), ("20%", 1), ("BOGO", 3)])

然后,下面的函数将使您得到非重复排列:

^{pr2}$

这是一个递归。在每个步骤中,我们选择项目重复次数。另外,我们避免在下一级递归中选择相同的项。在

对于您的问题实例,此代码比使用set的方法慢。但是,请尝试使用x = [1] * 30作为反例。在

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

相关问题 更多 >