10個のアイテムのすべての組み合わせを10％増分で見つけるより効率的な方法はありますか？

Question

私は分析している10通貨を持っており、これらの通貨の可能な組み合わせをすべて10％ずつ増やしたいと考えています。

合計が0％と100％との間の各通貨の任意の量で存在することができる100％ に合計しなければ、100％のように組み合わせた：たと​​えば次のよう

10% of A, 20% of B...etc 

制約があります

次のようにcurr_arrは、本質的に配列され

for element in itertools.product(*curr_arr): 
    if round(sum(element),1)==1: 
     comb_input.append(list(element)) 

：Aの私のコードは次のようになります。現時点では、有効な

です

[0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0] 

このアプローチは、すべての組み合わせを見て1に合ったものを抽出するため、非常に遅いです。これを実行してコードを高速化するより効率的な方法はありますか？

Answer 1

これは醜いですが、それは、速いです：

combinations = [] 
for a in xrange(11): 
    for b in xrange(11-a): 
     for c in xrange(11-a-b): 
      for d in xrange(11-a-b-c): 
       for e in xrange(11-a-b-c-d): 
        for f in xrange(11-a-b-c-d-e): 
         for g in xrange(11-a-b-c-d-e-f): 
          for h in xrange(11-a-b-c-d-e-f-g): 
           for i in xrange(11-a-b-c-d-e-f-g-h): 
            j = 10-a-b-c-d-e-f-g-h-i 
            combinations.append((a,b,c,d,e,f,g,h,i,j)) 
print len(combinations) 

はこれが0.2秒未満であなたのすべてのあなたの92378の組み合わせを提供します。

0から10までの整数値を返します。この整数値には、10を掛けてパーセント値を取得する必要があります。

Answer 2

実際には、問題は基本的にSubset sum problemです（整数のセットを指定すると、合計がkになります）。その問題はNP-Completeです。そして、それは今よりもはるかに優れたアルゴリズムを見つけるチャンスが非常に小さいことを意味します。

このコードの部分をPython拡張機能（C：Extending and Embedding the Python Interpreter）としてPythonコードから呼び出すことをお勧めします。それはあなたにまともなスピードの向上をもたらすはずです。

Answer 3

for currencyA, currencyB, currencyC, currencyD, currencyE, currencyF, currencyG, currencyH, currencyI, currencyJ in itertools.permutations(range(0,101,10)): 
    # you now have varying percentages of each currency 
    # if sum of the currencies == 100 
    # do whatever! 

Answer 4

100％を与えるすべての組み合わせを見つけて、それらの組み合わせのすべての順列を見つけるのはどうですか？私はあなたの例を実行することができませんでしたので、スピードの点でどのように比較するのかはわかりません。

import itertools 

curr_arr = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100] 

comb_input = [a for a in itertools.combinations_with_replacement(curr_arr, 10) if sum(a) == 100] 
comb_input = [set(itertools.permutations(a)) for a in comb_input] 

finish = [] 
for a in comb_input: 
    finish += list(a) 

print len(finish) 

Answer 5

フィルタリングせずに合計100％の組み合わせを直接生成することができます。 my answer to a previous question使用：

comb_input = [[x/10.0 for x in y] for y in lists_with_sum(10, 10)]