Tupel von ganzen Zahlen mit festen Summen bis hin zu Permutationen ⇐ Python

[Guest]

Ich bin mit dem folgenden Problem festgefahren, das ich in der Vergangenheit ein Stück Code beschleunigen muss, das ich geschrieben habe. Ich programmiere in Python, aber in dieser Frage geht es mehr um den Algorithmus als um den Python -Code. Verschiedene K -Tupel von Ganzzahlen mit Länge A und Summe d bis zur Permutation der Elemente der Tupel .
als Beispiel, wenn k = 2, a = 2 und d = 3, dies sind alle Sätze verschiedener K -Tupel von Ganzzahlen mit Länge A und Summe D: < /p>

Code: Select all

{(3,0), (0,3)}, {(3,0), (2,1)}, {(3,0), (1,2)}, {(1,2), (2,1)}, {(0,3), (2,1)}, {(0,3), (1,2)}

Ich möchte jedoch gleich die Sätze {(3,0), (1,2)} und {(0,3), (2,1)} betrachten , da ich durch den Austausch der beiden Zahlen im Tupel das gleiche Ergebnis erhalte. Am Ende sind alle Sätze von 2 verschiedenen Tupeln von Ganzzahlen mit Länge 2 und Sum 3: < /p>

Code: Select all

{(3, 0), (2, 1)}: 2,
{(3, 0), (1, 2)}: 2,
{(3, 0), (0, 3)}: 1,
{(2, 1), (1, 2)}: 1}
< /code>
Der Unterschied zur ersten Liste besteht darin, dass ich jetzt auch ein Etikett an die Sets angehängt habe, in dem ich zählt, wie viele Sätze bis zu Permutationen es gibt. Also, wieder {(3, 0), (2, 1)} 

wird mit einem 2 gekennzeichnet, da es auch zählt {(0, 3), (1, 2)} , während {(3, 0), (0, 3)} mit einem 1 gekennzeichnet ist, da die Permutationen einfach denselben Satz geben {(0, 3), (3, 0)} . 3 mit Summe 3). < /P>

Code: Select all

{(2, 1, 0), (3, 0, 0)}: 6, {(1, 2, 0), (3, 0, 0)}: 6, {(0, 3, 0), (3, 0, 0)}: 3, {(1, 1, 1), (3, 0, 0)}: 3, {(0, 2, 1), (3, 0, 0)}: 6, {(1, 2, 0), (2, 1, 0)}: 3, {(2, 0, 1), (2, 1, 0)}: 3, {(1, 1, 1), (2, 1, 0)}: 6, {(0, 2, 1), (2, 1, 0)}: 6, {(0, 1, 2), (2, 1, 0)}: 3
< /code>
Ich brauche einen Python -Iterator, der dieses Ergebnis erzeugt, mit k (die Anzahl der Tupel), A (die Länge jedes Tupels) und D (die Summe der Elemente in jedem Tupel) . 
Meine Frage (die ich hoffe, hat positive Antwort) ist: [b] Wurde dies schon irgendwo getan? [/b] 
Die engste Antwort i konnte diese Bibliothek finden, die ein allgemeineres [url=viewtopic.php?t=11587]Problem[/url] löst, aber mit k = 1 (sie listet nur Tupel auf, nicht die Lenght -K -Sätze von Tupeln). < /p>
[b] in Der unglückliche Fall, den dies noch nie zuvor getan wurde. Hier sind meine Versuche, eine Lösung zu erzeugen. /em>. Dies liegt daran, dass  beide Ansätze, die ich ausprobiert habe, einfach falsch sind. Die zweite funktioniert einfach nicht, aber nicht wegen der Programmierung, sondern wegen des Algorithmus, was falsch ist.  Für Ihre Bequemlichkeit /Neugier füge ich einen in Python3 geschriebenen Beispielcode hinzu (wenn ich einen Arbeitscode erstellen kann, werde ich ihn natürlich gerne teilen!) < /P>
 Mein erster - nutzlos - Ansatz  bestand nur darin, das Ergebnis zu konstruieren, indem sie alle Sätze iteriert und dann Permutationen anwendet, um die Liste zu reduzieren. Dies ist zu langsam und Speicherverbrauch. (Ein Beispielcode, dies funktioniert wiederum, aber es ist kein Iterator) 
 Mein zweites - unvollendeter - Ansatz  war hoffentlich etwas klug: (ein Beispielcode, Dies funktioniert nicht, siehe die Erklärung unten) < /p>

[*] Erster Schritt iteriere ich über die geordneten Tupel von Ziffern: für k = 2, a = 3, d = 3 Ich bekomme nur (3,0,0), (2, 1, 0), (1, 1, 1) 

.
[*] Zweiter Schritt, ich mache fort, eine Liste von Ziffern zu erstellen Dies wird die endgültigen Tupel komponieren: Zuerst verwende ich (3,0,0) zweimal, dann (3,0,0) und (2,1,0) , dann (dann (( 3,0,0) und (1,1,1) usw. Ich mache das mit einer Rekursion. Hier sind drei Beispiele: < /li>
< /ul>

• Ziffern (3,0,0) < /code> zweimal. Das erste Tupel ist nur (3,0,0) (da ich bis zur Permutation arbeite). Für das zweite Tupel muss ich mich daran erinnern, dass der erste zwei Nullen hat, damit ich die zweite und die dritte Ziffern austauschen kann, und ich erstelle das Set {{

  Code: Select all

  (3,0,0)

  , (0,3,0) }
• Ziffern (3,0,0) und (2,1,0)