我能找到一个10公里以上整数的幂集的和的最快方法是什么?
long_list = [randrange(0,10000) for r in xrange(10000)]
desired_sum = sum(randint(0,10000)+randint(0,10000)+randint(0,10000))
def powerset(iterable):
# notice the '3' in combinations(s,3), taking all combinations of 3.
s = list(iterable)
return chain.from_iterable(combinations(s, 3) for r in range(len(s)+1))
ps = powerset(set(long_list))
if desired_sum > 29994:
print "cannot compute"
else:
for i in ps:
if sum(i) == desired_sum: # last combination of chain 9999+9998+9997
print i
我的电脑计算时间太长,我想问一些关于如何处理这样的大型组合的提示。
为了这样搜索,在定义组合的和之前,我的for循环必须先耗尽整个列表。
找到了最快的解决方案。在
在我的机器上一秒钟之内就可以运行了。这个解决方案的优点在于,对于任何数量的匹配和的项,都可以用递归来推广。在
本genexpr:
…只是反复生成相同的组合,len(s)次。那不是动力装置。更重要的是,这只是浪费精力;如果没有一个组合匹配,那么这些组合的不同副本中的组合也不会匹配。在
因此,您可以通过不添加额外的工作来优化:
^{pr2}${1{1}调用这个列表大约需要10000个成员,这样你就可以得到一个很长的列表了。在
如果知道所需的和,只需遍历所有对(
combinations(s, 2)
),并测试缺少的元素是否在集合中示例感谢@thefourtheye
相关问题 更多 >
编程相关推荐