0

レガシー レポートをリバース エンジニアリングし、python を使用して問題を解決しようとしています。

従来のレポートの最終合計数は 200,000 です。

この 200k に達する可能性のある数値のコレクションを知っていますが、このコレクションには、除外する必要がある他の多くの数値が散らばっています (ロジックはまだ理解していません)。

Python では、数値のリストを繰り返し処理して、合計が 200k になる可変長 (1 要素 = 200k、または 15 要素の積) のすべてのエントリ (サブリスト) を見つけるにはどうすればよいですか? ?

私はそれを書き始めましたが、要素 #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(あなたのコレクション)からのエントリpermutations(iterable, r)を含むすべての可能な順列を見つけようとすることができます。それらの合計は (たとえば で) 簡単に取得できます。riterablenumpy.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 に答える