搜索iterable链组合的最快方法？

Question

我能找到一个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循环必须先耗尽整个列表。

Answer 1

找到了最快的解决方案。在

from random import randrange
long_list = [randrange(0,10000) for r in xrange(10000)]

def main():
    myList, result = sorted(set(long_list), reverse = True), []
    myLen = len(myList)
    for i in xrange(myLen):
        for j in xrange(i + 1, myLen):
            if 29994 - (myList[i] + myList[j]) > myList[j]: break
            for k in xrange(j + 1, myLen):
                tsum = myList[i] + myList[j] + myList[k]
                if tsum < 29994:
                    break
                elif tsum == 29994:
                    result.append((myList[i], myList[j], myList[k]))
    print result
    return result

import cProfile
cProfile.run("main()")

在我的机器上一秒钟之内就可以运行了。这个解决方案的优点在于，对于任何数量的匹配和的项，都可以用递归来推广。在

Answer 2

本genexpr：

(combinations(s, 3) for r in range(len(s)+1))

…只是反复生成相同的组合，len（s）次。那不是动力装置。更重要的是，这只是浪费精力；如果没有一个组合匹配，那么这些组合的不同副本中的组合也不会匹配。在

因此，您可以通过不添加额外的工作来优化：

^{pr2}$

{1{1}调用这个列表大约需要10000个成员，这样你就可以得到一个很长的列表了。在

Answer 3

如果知道所需的和，只需遍历所有对（combinations(s, 2)），并测试缺少的元素是否在集合中

示例感谢@thefourtheye

from random import randrange
from itertools import combinations
long_list = [randrange(0,10000) for r in xrange(10000)]

def powerset(it):
    return [(i[0], i[1], 29994 - sum(i)) for i in combinations(it, 2) if 29994 - sum(i) in it]

def main():
    print powerset(set(long_list))

import cProfile
cProfile.run("main()")