Gibt es eine effizientere Möglichkeit, alle Kombinationen von 10 Elementen in 10% -Schritten zu finden?

Question

Ich habe 10 Währungen, die ich analysiere, und ich möchte alle möglichen Kombinationen dieser Währungen in 10% -Schritten finden. Zum Beispiel:

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

Die Randbedingungen sind wie folgt:

die Gesamtmenge bis zu 100% summieren hat es eine Menge jeder Währung zwischen 0% und 100%, so dass eine Kombination von 100% liegen kann eines gültigen

im Moment ist mein Code sieht wie folgt aus:

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

Wo curr_arr ist im wesentlichen ein Array wie folgt:

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

Dieser Ansatz ist sehr langsam, weil er alle Kombinationen betrachtet und dann diejenigen extrahiert, die sich zu einer Summe addieren. Gibt es eine effizientere Möglichkeit, dies zu tun und meinen Code zu beschleunigen?

Answer 1

Das ist hässlich, aber es ist schnell:

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) 

Dies gibt Ihnen alle 92.378 Kombinationen in weniger als 0,2 Sekunden.

Beachten Sie, dass es die ganzzahligen Werte zwischen 0 und 10 zurückgibt, die mit 10 multipliziert werden müssen, um Prozentsätze zu erhalten.

Answer 2

Nicht wirklich, Ihr Problem ist im Grunde die Subset sum problem (angesichts einer Reihe von ganzen Zahlen, finden Sie diejenigen, die Summe zu k) und das Problem ist NP-Complete. Und das bedeutet, dass Ihre Chancen, einen wesentlich besseren Algorithmus zu finden als Sie jetzt haben, sehr gering sind.

Ich würde empfehlen, diesen Teil des Codes in C als eine Python-Erweiterung zu schreiben (siehe Extending and Embedding the Python Interpreter) und diese Funktion aus Ihrem Python-Code aufrufen. Das sollte dir eine ordentliche Geschwindigkeitsverbesserung geben.

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

Wie wäre es, alle Kombinationen zu finden, die 100% ergeben und dann alle Kombinationen dieser Kombinationen finden? Ich konnte dein Beispiel nicht ausführen, daher bin ich mir nicht sicher, wie es in Bezug auf die Geschwindigkeit aussieht.

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

Es ist möglich, die Kombinationen, die sich zu 100% addieren, direkt ohne Filterung zu erzeugen. Mit my answer to a previous question:

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