Ich habe es schwer, 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};
Das wird in drei Mengen von Zahlen platziert, mit der einzigen Einschränkung, dass jede Menge mindestens einen Wert enthält und jeder Wert nur einmal verwendet werden kann. Bearbeiten: Alle 8 Zahlen sollten verwendet werden
Zum Beispiel:
R1 [] = {1, 4}
R2 [] = {2, 8, 5, 6}
R3 [] = {7, 3}
Ich muss alle möglichen Kombinationen eines Satzes R1, R2, R3 durchlaufen. Reihenfolge 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?
Ich habe vor mir Knuth Band 4, Fascicle 3, Generieren aller Kombinationen und Partitionen , Abschnitt 7.2.1.5 Erzeugen aller gesetzten Partitionen (Seite 61 in fascicle) .
Zuerst beschreibt er Algorithmus H, Eingeschränkte Wachstumsstrings in lexikographischer Ordnung aufgrund von 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 festgelegte Partitionen denkt er nach:
Angenommen, wir sind nicht an allen der Partitionen interessiert; wir wollen vielleicht nur diejenigen, die m Blöcke haben. Können wir dies durch die kleinere Sammlung beschränkter Wachstumszeichenfolgen tun, die sich immer noch um eine Ziffer ändern?
Dann gibt er eine Lösung für Frank Ruskey bekannt.
Die einfache (und sicherlich korrekte) Lösung besteht darin, den Algorithmus H auf Partitionen zu codieren, bei denen m==3 und keine der Partitionen die leere Menge ist (entsprechend den 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 die leere Menge 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 der verbleibenden fünf erweitern 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 Sie keine eigene Klugheit überprüfen müssen, und Sie Ihre Meinung später über Ihre Einschränkungen ändern, ohne Ihre Klugheit überarbeiten zu müssen.
Ich könnte später sogar eine Lösung finden, aber das ist alles für den Moment.
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 in Ссылка
Wahrscheinlich nicht der beste Ansatz, aber es sollte funktionieren.
Bestimmen Sie die Anzahl der Kombinationen von drei Zahlen, die zu 8 summieren:
%Vor%Um das oben genannte zu finden, habe ich angefangen mit:
%Vor%mit dem Wissen, dass weniger als die Hälfte 2 ist, müssen alle Kombinationen gefunden worden sein ... aber da die Liste nicht lang ist, können wir auch bis zum Ende gehen.
Sortiere nun jede Liste von 3 von der größten bis 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).
Betrachten Sie nun eine Liste in der obigen Menge
6,1,1 alle möglichen Kombinationen werden gefunden durch:
8 pick 6, (da wir sechs ausgewählt haben, gibt es nur noch zwei zur Auswahl) 2 pick 1, 1 pick 1 was zu 28 * 2 * 1 = 56 funktioniert, ist es wert zu wissen, wie viele Möglichkeiten es gibt, damit du es testen kannst.
n wähle r (nimm r Elemente aus n Gesamtoptionen)
n C r = n! / [(n-r)! r!]
Nun haben Sie die Gesamtzahl der Iterationen für jede Komponente der Liste für die erste, es ist 28 ...
Wenn Sie 6 Elemente von 8 auswählen, entspricht das dem Erstellen einer Liste von 8 minus 2 Elementen, aber welchen zwei Elementen?
Wenn wir 1,2 entfernen, bleibt uns 3,4,5,6,7,8 übrig. 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.
%Vor%Summierung jeder der obigen Spalten gibt uns 28. (so dass dies nur die erste Ziffer in der Liste (6,1,1) abgedeckt, wiederholen Sie den Vorgang für die zweite Ziffer (a one), die "2 Wählen Sie 1" So ist von 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ß, dass dies kein detaillierter Algorithmus ist, aber ich hoffe, dass Sie anfangen können.
Wenden Sie das Problem auf den Kopf und Sie werden eine einfache Lösung finden. 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.
Die triviale Implementierung würde 8 for-Schleifen und einige IFs (Pseudocode) beinhalten:
%Vor%Es kann auch rekursiv implementiert werden, indem zwei Arrays und einige Funktionen verwendet werden. Viel netter und einfacher zu debuggen / folgen (Pseudocode):
%Vor%Die dritte Implementierung würde keine Rekursion und ein bisschen Backtracking verwenden. Pseudocode, wieder:
%Vor%Generieren Sie alle Kombinationen von Teilmengen rekursiv auf klassische Weise. Wenn Sie den Punkt erreichen, an dem die Anzahl der verbleibenden Elemente der Anzahl der leeren Teilmengen entspricht, beschränken Sie sich nur auf die leeren Teilmengen.
Hier ist eine Python-Implementierung:
%Vor%Und ein Test:
%Vor%Tags und Links algorithm loops permutation