我正在寻找列表的唯一排列,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
然而,这需要太长的时间来运行,我想知道是否有人可以给我更多 有效的解决方案。在
运行它需要很长时间的原因是,当您向列表添加元素时,每次查找都要花费较长的时间,因为它必须(平均)搜索列表的一半。更好的方法是使用字典:
以及:
^{pr2}$这将利用hash maps的查找性能。在
如果您只是在进行成员资格测试,请按照DSM的建议使用集合。在
关于使用快速集合结构的建议是很好的,但是如果你不生成一开始就不需要的项目,你会得到最好的结果。让我们对
x
做一个稍微不同的表示:然后,下面的函数将使您得到非重复排列:
^{pr2}$这是一个递归。在每个步骤中,我们选择项目和重复次数。另外,我们避免在下一级递归中选择相同的项。在
对于您的问题实例,此代码比使用
set
的方法慢。但是,请尝试使用x = [1] * 30
作为反例。在if i not in combos:
将花费很长时间,因为列表中的成员资格测试是(最坏情况下)O(N),它必须扫描每个元素。您可以使用set
代替:相关问题 更多 >
编程相关推荐