是否有更高效的方式以10％的增量找到10個項目的所有組合？

我有10種貨幣我正在分析，我想以10％的增量找到這些貨幣的所有可能的組合。例如：是否有更高效的方式以10％的增量找到10個項目的所有組合？

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

約束如下：

總有總結爲100％可以有各貨幣的0％和100％之間的任何量，所以100％的組合A是有效

目前我的代碼看起來是這樣的：

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

哪裏curr_arr本質上是一個數組如下：

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

這種方法非常慢，因爲它會查看所有組合，然後提取合計爲一的組合。有沒有更有效的方法來加快我的代碼？

來源

2012-03-29 Mandeep

如果可能，請使用百分比（10,20,30，...）而不是浮點數（0.1,0.2,0.3，...）。這些浮點數並不總和爲1.0 .:'0.3 + 0.3 + 0.3 + 0.1'返回'0.99999999999999989' – eumiro 2012-03-29 07:50:57

這是醜陋的，但它是快速：

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來得到百分比。

來源

2012-03-29 08:33:56 eumiro

我已經只是用range而不是xrange來試試這個，每行顯示總和爲11或110％。它應該是xrange（10）嗎？ – Mandeep 2012-03-29 09:03:04

@ Mandeep - 不，它是計算'j'的行中的11 - > 10。對不起。現在修復。 xrange中的11是正確的。 – eumiro 2012-03-29 09:07:33

好的，謝謝，讓我試試 – Mandeep 2012-03-29 09:12:21

不是，你的問題基本上是Subset sum problem（給定一組整數，找到總和爲k的那些），那個問題是NP-Complete。這意味着您找到比現在更好的算法的機會非常小。

我建議在C中將這部分代碼作爲Python擴展（請參閱Extending and Embedding the Python Interpreter），並從Python代碼中調用該函數。這應該給你一個體面的速度提高。

來源

2012-03-29 07:50:46

好的，謝謝，我想解決這個問題的最快方法是運行一次代碼以找到所有組合。將其導出爲excel並過濾那些總和爲100％的數據，然後每次運行分析時重新導入這些組合 – Mandeep 2012-03-29 08:08:23

@Mandeep - 您不想將10 ** 10個數據條目導出爲excel ... – eumiro 2012-03-29 08:25:47

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!

來源

2012-03-29 07:51:53 inspectorG4dget

如何找到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)

來源

2012-03-29 08:16:30 Fenikso

可以直接生成總和爲100％的組合，無需過濾。使用my answer to a previous question：

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

來源

2012-03-29 08:33:15

是否有更高效的方式以10％的增量找到10個項目的所有組合？

回答

相關問題