0

我正在尝试对遗留报告进行逆向工程并使用 python 来解决问题。

旧报告的最终总数为 200,000。

我知道一个可能最终达到 200k 的数字集合，但是这个集合中到处都是要过滤掉的许多其他数字（逻辑我还不明白）。

在 python 中，我如何遍历数字列表以找到所有可变长度的条目（子列表）（可能是 1 个 = 200k 的元素，或 15 个元素的乘积......），总和为 200k ?

我开始把它写出来，然后当我意识到元素 #1 + 2 可能溢出但列表元素 #1 + 4 + 7 可能与 200k 匹配时决定寻求帮助....

这几乎就像因式分解，但是使用总和而不是乘积，并且在可能的候选者列表中。

没有把握。有任何想法吗？有人做过这样的事吗？

附加细节：
通过排列和numpy，我得到了预期的结果，但是预期的输入和输出花费的时间太长了。（即天..？）

下面是我所在的位置：

下面似乎给出了正确的结果，尽管它似乎需要一段时间。

我会接受上面的答案，让它通宵达旦。

谢谢，

from itertools import permutations 
import numpy , pickle, random
output_results = {} 
input_array = [random.randrange(0,15000) for i in range(1000)]
desired_sum = 200000
#input_array = (1,2,9,13,12) 
#desired_sum = 23 

for r in range(1,len(input_array)): 
    for p in permutations(input_array, r):
        temp_sum = numpy.sum(p) 
        if temp_sum == desired_sum: 
            output_results[p] = numpy.sum(p) 
    if r % 10 == 0:
        print "Finished up to number %s " % r 

pickle.dump( output_results, open( "save.p", "wb" ) )
4

1 回答 1

1

Itertools.permutations可以提供帮助。

r改变in的值，permutations(iterable, r)您可以尝试从（您的集合）中找到包含r条目的所有可能排列，您可以轻松地获得其中的总和（例如，使用）。iterablenumpy.sum

如果您对预期的内容有所了解并为您设置了合理的上限，r您应该在合理的时间内得到答案

编辑

@joefromct：您可以通过以下方式首先估计找到所需解决方案所需的最大值r（未经测试，但想法应该是正确的）

sorted_input = np.sorted(input_array)
cumsum = np.cumsum(sorted_input)
max_r = (cumsum<desired_sum).sum()
if max_r == len(input_array) and sorted_input[-1] < desired_sum:
    print("sorry I can't do anything for you")
    exit()

for r in range(1,max_r):
    [...]
于 2013-02-04T17:40:22.480 回答