Ich habe versucht, einen Weg zu finden, um alle Partitionen mit der Größe n eines Multisets zu generieren, bin aber bisher mit leeren Händen davongekommen. Lassen Sie mich zuerst zeigen, was ich zu archivieren versuche.

Nehmen wir an, wir haben einen Eingabevektor vonuint32_t:

std::vector<uint32_t> input = {1, 1, 2, 2}

Angenommen, wir möchten alle unterschiedlichen Partitionen in zwei Größen erstellen. Es gibt nur zwei davon, nämlich:

[[1, 1], [2, 2]], [[1, 2], [1, 2]]

Beachten Sie, dass die Reihenfolge keine Rolle spielt, d. H. Alle der folgenden sind doppelte, falsche Lösungen.

Duplizieren, da die Reihenfolge innerhalb einer Permutationsgruppe keine Rolle spielt:

[[2, 1], [1, 2]]

Duplizieren, da die Reihenfolge der Gruppen keine Rolle spielt:

[[2, 2], [1, 1]]

Nicht irgendwelche Hausaufgaben BTW. Ich bin darauf gestoßen, als ich etwas bei der Arbeit programmiert habe, aber jetzt ist es aus persönlichem Interesse, dass ich wissen möchte, wie ich damit umgehen soll. Die Parameter für das arbeitsbedingte Problem waren so klein, dass es nicht wirklich darauf ankam, ein paar tausend Dubletten zu generieren.

Aktuelle Lösung (erzeugt Duplikate)

Um zu veranschaulichen, dass ich nicht nur frage, ohne versucht zu haben, eine Lösung zu finden, möchte ich versuchen, meinen aktuellen Algorithmus zu erläutern (der bei Verwendung mit Multisets doppelte Lösungen erzeugt).

Es funktioniert wie folgt: Der Status hat einen Bitsatz, bei dem für jeden Partitionsblock n Bits auf 1 gesetzt sind. Die Länge der Bitsätze beträgtsize(input) - n * index_block(), z.B. Wenn der Eingangsvektor 8 Elemente und n = 2 hat, verwendet der erste Partitionsblock einen 8-Bit-Bitsatz mit 2 auf 1 gesetzten Bits, der nächste Partitionsblock verwendet einen 6-Bit-Bitsatz mit 2 auf 1 gesetzten Bits usw.

Aus diesen Bitsätzen wird eine Partition erstellt, indem die einzelnen Bitsätze der Reihe nach durchlaufen und die Elemente des Eingabevektors mit Indizes extrahiert werden, die der Position von 1-Bits im aktuellen Bitsatz entsprechen.

Um die nächste Partition zu generieren, durchlaufe ich die Bitsätze in umgekehrter Reihenfolge. Die nächste Bitmengenpermutation wird berechnet (unter Verwendung einer Umkehrung von Gospers Hack). Wenn das erste Bit in dem aktuellen Bitsatz nicht gesetzt ist (d. H. Der Vektorindex 0 ist nicht ausgewählt), wird dieser Bitsatz in seinen Anfangszustand zurückgesetzt. Das Erzwingen, dass das erste Bit immer gesetzt ist, verhindert das Erzeugen von Duplikaten beim Erzeugen von Partitionen mit einer Größe von n (Duplikate der oben gezeigten zweiten Art). Wenn der aktuelle Bitsatz gleich seinem Startwert ist, wird dieser Schritt für den vorherigen (längeren) Bitsatz wiederholt.

Dies funktioniert hervorragend (und sehr schnell) für Sets. Bei Verwendung mit Multisets werden jedoch doppelte Lösungen generiert, da nicht bekannt ist, dass beide Elemente im Eingabevektor mehr als einmal vorkommen. Hier ist ein Beispiel für die Ausgabe:

std::vector<uint32_t> input = {1, 2, 3, 4};
printAllSolutions(myCurrentAlgo(input, 2));
=> [[2, 1], [4, 3]], [[3, 1], [4, 2]], [[4, 1], [3, 2]]

std::vector<uint32_t> input = {1, 1, 2, 2};
printAllSolutions(myCurrentAlgo(input, 2));
=> [[1, 1], [2, 2]], [[2, 1], [2, 1]], [[2, 1], [2, 1]]

Diese letzte (doppelte) Lösung wird nur generiert, weil der Algorithmus keine Duplikate in der Eingabe kennt. Sie generiert in beiden Beispielen genau dieselben internen Zustände (d. H. Welche Indizes ausgewählt werden sollen).

Gewünschte Lösung

Ich denke, es ist mittlerweile ziemlich klar, womit ich am Ende fertig werden will. Der Vollständigkeit halber würde es ungefähr so aussehen:

std::vector<uint32_t> multiset = {1, 1, 2, 2};
MagicClass myGenerator(multiset, 2);
do {
  std::vector<std::vector<uint32_t> > nextSolution = myGenerator.getCurrent();
  std::cout << nextSolution << std::endl;
} while (myGenerator.calcNext());
=> [[1, 1], [2, 2]]
   [[1, 2], [1, 2]]

D. der Code würde ungefähr so funktionieren wiestd::next_permutation, informiert darüber, dass alle Lösungen generiert wurden und bei der "ersten" Lösung geendet haben (für jede Definition der ersten, die Sie verwenden möchten, wahrscheinlich lexikografisch, muss es aber nicht sein).

Der am nächsten verwandte Algorithmus, den ich gefunden habe, ist Algorithmus M aus Knuths The Art of Computer Programming, Band 4, Teil 1, Abschnitt 7.2.1.5 (S. 430). Dadurch werden jedoch alle möglichen Multiset-Partitionen generiert. Das Buch enthält auch eine Übung (7.2.1.5.69, Lösung auf S. 778) zum Ändern von Alg. M, um nur Lösungen mit höchstens r Partitionen zu generieren. Dies ermöglicht jedoch weiterhin Partitionen unterschiedlicher Größe (z. B.[[1, 2, 2], [1]] wäre eine gültige Ausgabe für r = 2).

Irgendwelche Ideen / Tricks / vorhandenen Algorithmen, wie man das macht? Beachten Sie, dass die Lösung effizient sein sollte, dh alle zuvor generierten Lösungen im Auge zu behalten, herauszufinden, ob es sich bei der aktuell generierten Lösung um eine Permutation handelt, und diese zu überspringen, ist aufgrund der Geschwindigkeit, mit der der Lösungsraum bei längeren Eingaben mit mehr explodiert, nicht möglich Duplikate.