Schleife durch verschiedene Sätze von einzigartigen Permutationen

Question

Ich habe eine harte Zeit, mit dem Layout-Code für dieses Problem zu beginnen.

Ich habe eine feste Anzahl von Zufallszahlen, in diesem Fall 8 Zahlen. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Diese werden in 3 Mengen von Zahlen platziert, mit der einzigen Einschränkung, dass jeder Satz mindestens einen Wert enthält und jeder Wert nur einmal verwendet werden kann. Edit:

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

: Alle 8 Zahlen sollten

beispielsweise verwendet werden

R3 [] = {7, 3}

Ich muss alle möglichen Kombinationen eines Satzes R1, R2, R3 durchlaufen. Bestellen Sie ist nicht wichtig, also wenn das obige Beispiel passiert ist, brauche ich nicht

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

Was ist eine gute Methode?

Answer 1

Wahrscheinlich nicht der beste Ansatz, aber es sollte funktionieren.

Bestimmen Anzahl von Kombinationen von drei Zahlen, die Summe bis 8:

1,1,6 
1,2,5 
1,3,4 
2,2,4 
2,3,3 

Um die oben finde ich mit gestartet:

6,1,1 then subtracted 1 from six and added it to the next column... 
5,2,1 then subtracted 1 from second column and added to next column... 
5,1,2 then started again at first column... 
4,2,2 carry again from second to third 
4,1,3 again from first... 
3,2,3 second -> third 
3,1,4 

zu wissen, dass weniger als die Hälfte 2 alle Kombinationen gewesen sein muss gefunden ... aber da die Liste nicht lang ist, können wir genauso gut zum Ende gehen.

Sortieren Sie nun jede Liste von 3 von der größten zur kleinsten (oder umgekehrt) Sortieren Sie nun jede Liste von 3 relativ zueinander. Kopieren Sie jede eindeutige Liste in eine Liste eindeutiger Listen. Wir haben jetzt alle Kombinationen, die zu 8 hinzufügen (fünf Listen, die ich denke).

8 Pick 6, (da wir sechs gepflückt gibt es nur 2 übrig zur Auswahl:

nun eine Liste in der obigen Satz betrachten

6,1,1 alle möglichen Kombinationen werden durch gefunden) 2 pick 1, 1 pick 1 was auf 28 * 2 * 1 = 56 funktioniert, es lohnt sich zu wissen, wie viele Möglichkeiten es gibt, damit man testen kann.

n wählen r

n C r = n (r Elementen aus n insgesamt Optionen wählen)!/[(n-r)! r!]

So, jetzt haben Sie die Gesamtzahl der Iterationen für jede Komponente der Liste für die erste es 28 ...

Nun Kommissionierung 6 Veröffentlichungen von 8 ist die gleiche wie die Erstellung einer Liste von 8 minus 2 Elemente, aber welche zwei Elemente?

Nun, wenn wir 1,2 entfernen, die uns mit 3,4,5,6,7,8 verlässt. Betrachten wir alle Gruppen von 2 ... Beginnend mit 1,2 wäre der nächste Wert 1,3 ... also wird das Folgende Spalte für Spalte gelesen.

12 
13 23 
14 24 34 
15 25 35 45 
16 26 36 46 56 
17 27 37 47 57 67 
18 28 38 48 58 68 78 

jeder der oben genannten Spalten Fasst gibt uns 28 (so dies betraf nur die erste Ziffer in der Liste (6,1,1) wiederholen Sie den Vorgang für die zweite Stelle (eine Eins), die „2 Wählen Sie 1 "Also aus der linken über zwei Ziffern aus der obigen Liste wählen wir eine von zwei und dann für die letzte wählen wir die verbleibende.

Ich weiß, das ist kein detaillierter Algorithmus, aber ich hoffe, Sie können

Answer 2

Generieren Sie alle Kombinationen von Teilmengen rekursiv auf die klassische Art. Wenn Sie den Punkt erreichen, an dem die Anzahl der verbleibenden Elemente der Anzahl der leeren Teilmengen entspricht, dann Beschränke dich nur auf die leeren Subsets.

Hier ist eine Python-Implementierung:

def combinations(source, n): 
    def combinations_helper(source, subsets, p=0, nonempty=0): 
    if p == len(source): 
     yield subsets[:] 
    elif len(source) - p == len(subsets) - nonempty: 
     empty = [subset for subset in subsets if not subset] 
     for subset in empty: 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+1): 
      yield combination 
     subset.pop() 
    else: 
     for subset in subsets: 
     newfilled = not subset 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled): 
      yield combination 
     subset.pop() 

    assert len(source) >= n, "Not enough items" 
    subsets = [[] for _ in xrange(n)] 
    for combination in combinations_helper(source, subsets): 
    yield combination 

Und ein Test:

>>> for combination in combinations(range(1, 5), 2): 
... print ', '.join(map(str, combination)) 
... 
[1, 2, 3], [4] 
[1, 2, 4], [3] 
[1, 2], [3, 4] 
[1, 3, 4], [2] 
[1, 3], [2, 4] 
[1, 4], [2, 3] 
[1], [2, 3, 4] 
[2, 3, 4], [1] 
[2, 3], [1, 4] 
[2, 4], [1, 3] 
[2], [1, 3, 4] 
[3, 4], [1, 2] 
[3], [1, 2, 4] 
[4], [1, 2, 3] 
>>> len(list(combinations(range(1, 9), 3))) 
5796 

Answer 3

ich vor mir Volume Knuth haben 4, Faszikel 3, Generieren alle Kombinationen und Partitionen, Abschnitt 7.2 .1.5 Generieren aller eingestellten Partitionen (Seite 61 in fascicle).

Erste Details er Algorithmus H, Restricted Wachstum Strings in lexikographische Ordnung aufgrund George Hutchinson. Es sieht einfach aus, aber ich werde mich jetzt nicht damit befassen.

Auf der nächsten Seite unter einer Ausarbeitung Gray-Codes für Set-Partitionen er sinniert:

Es sei aber, dass wir alle der Partitionen in nicht interessiert sind; wir wollen vielleicht nur diejenigen, die m Blöcke haben. Können wir dies durch die kleinere Sammlung beschränkter Wachstumssketten durchführen, die sich immer noch um eine Ziffer ändern?

Dann er Details eine Lösung aufgrund Frank Ruskey.

Die einfache Lösung (und gewiss, um richtig zu sein) ist, Algorithmus H Filterung auf Partitionen zu kodieren, wo m==3 und keine der Partitionen die leere Menge sind (gemäß Ihren angegebenen Einschränkungen). Ich vermute, dass Algorithmus H rasend schnell läuft, so dass die Filterkosten nicht groß sein werden.

Wenn Sie dies auf einem 8051 implementieren, können Sie mit dem Ruskey-Algorithmus beginnen und dann nur nach Partitionen filtern, die den leeren Satz enthalten.

Wenn Sie dies auf etwas implementieren, das kleiner als 8051 und Millisekunden ist, können Sie jede der drei Partitionen mit einem eindeutigen Element (einer einfachen verschachtelten Schleife aus drei Ebenen) versehen und dann durch Partitionierung auf den verbleibenden erweitern fünf Elemente für m==3 mit dem Ruskey-Algorithmus. Sie müssen nichts filtern, aber Sie müssen nachverfolgen, welche fünf Elemente noch zu partitionieren sind.

Das Schöne am Herausfiltern aus dem allgemeinen Algorithmus ist, dass man keine eigene Klugheit verifizieren muss, und man seine Meinung später über seine Einschränkungen ändert, ohne seine Klugheit überarbeiten zu müssen.

Ich könnte sogar später eine Lösung arbeiten, aber das ist alles für jetzt.

P.S. für die Java-Guppys: Ich entdeckte auf "George Hutchison restricted growth strings" ein bestimmtes Paket ca.ubc.cs.kisynski.bell mit Dokumentation für die Methode growthStrings(), die den Hutchison-Algorithmus implementiert.

Erscheint bei http://www.cs.ubc.ca/~kisynski/code/bell/

Answer 4

Schalten Sie das Problem auf dem Kopf und Sie finden eine Straight-Forward-Lösung zur Verfügung stehen. Sie haben 8 Nummern, die jeweils genau einer Gruppe zugeordnet werden müssen. Die "Lösung" ist nur dann eine Lösung, wenn jeder Gruppe mindestens eine Nummer zugewiesen wurde.

for num1 in [1,2,3] 
    for num2 in [1,2,3] 
    for num3 in [1,2,3] 
     ... 
     if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3)) 
      Print Solution! 

Es kann auch rekursiv durchgeführt werden, unter Verwendung von zwei Arrays und ein paar Funktionen:

Die triviale Implementierung 8 für Schleifen und ein paar IFs (Pseudo-Code) beinhalten würde. Viel schöner und einfacher zu debuggen/Follow (Pseudo-Code):

numbers = [1, 2, 3, 4, 5, 6, 7, 8] 
positions = [0, 0, 0, 0, 0, 0, 0, 0] 

function HandleNumber(i) { 
    for position in [1,2,3] { 
    positions[i] = position; 
    if (i == LastPosition) { 
     // Check if valid solution (it's valid if we got numbers in all groups) 
     // and print solution! 
     } 
    else HandleNumber(i+1) 
    }  
} 

Die dritte Implementierung keine Rekursion und ein wenig Rückzieher verwenden würde. Pseudocode, wieder:

numbers = [1,2,3,4,5,6,7,8] 
groups = [0,0,0,0,0,0,0,0] 

c_pos = 0 // Current position in Numbers array; We're done when we reach -1 
while (cpos != -1) { 
    if (groups[c_pos] == 3) { 
     // Back-track 
     groups[c_pos]=0; 
     c_pos=c_pos-1 
    } 
    else { 
    // Try the next group 
    groups[c_pos] = groups[c_pos] + 1 
    // Advance to next position OR print solution 
    if (c_pos == LastPostion) { 
     // Check for valid solution (all groups are used) and print solution! 
     } 
    else 
     c_pos = c_pos + 1 
    } 
}