Mögliche Kombinationen erzeugen
-
Hallo,
ich habe ein kleines immer wiederkehrendes Problem, was mich einfach nicht in Ruhe lässt.
Es geht im Prinzip darum alle möglichen Kombinationen von x Items zu generieren.
Wenn es keinerlei Regeln bezüglich den Kombinationen gibt, ist mir die Berechnung klar. Die Anzahl der Möglichkeiten ist x hoch x. Das lässt sich auch einfach z.B. mit verschachtelten Schleifen programmieren, denn jeder increment der innersten Schleife führt zu einer neuen gültigen Möglichkeit.
Aber angenommen, die Möglichkeiten sind so begrenzt, dass pro Möglichkeit ein Item auch nur einmal vorkommen darf. Die Anzahl wäre dann ja die Fakultät von x.
Das lässt sich nicht mehr so einfach programmieren, denn es gibt die Möglichkeit vom einfachen Fall nicht mehr, direkt mit einem Schleifenincrement zu einer gültigen Lösung zu springen. Man generiert also ungültige Möglichkeiten, die man prüfen muss, ob sie gültig sind, wenn man den Ansatz mit den Schleifen verfolgt, oder muss prüfen, welche Schleife man um wieviel incrementieren muss um die nächste gültige Lösung zu erreichen...
Seht ihr für den Fall eine Lösung, oder ist es quasi unausweichlich, dass man Lösungen generiert, die auf ihre Gültigkeit hin geprüft werden müssen? Kann man irgendwie den "Abstand" zwischen den Lösungen bei der Fakultät berechnen?
MfG
-
https://en.wikipedia.org/wiki/Permutation
Wenn du das Konzept erst einmal verstanden hast, solltest du auch von alleine auf jede Menge Algorithmen kommen, die so etwas gezielt erzeugen können.
-
Als Library gibt es [https://github.com/mraggi/discreture] für Kombinationen.
std::next_permutationgibt es für dein Beispiel mit der Fakultät.
-
@SeppJ sagte in Mögliche Kombinationen erzeugen:
https://en.wikipedia.org/wiki/Permutation
Wenn du das Konzept erst einmal verstanden hast, solltest du auch von alleine auf jede Menge Algorithmen kommen, die so etwas gezielt erzeugen können.
Ja, das sollte ich...
Allerdings sehe ich keine Lösung dafür, aus der Menge aller Kombinationen in natürlicher Reihenfolge, die Permutationen durch eine Formel zu addressieren, sondern nur einen Algorithmus dafür zu verwenden.
Möchte ich eine nächste Permutation (in letzter Konsequenz) durch einen simplen increment selektieren, brauche ich eine Tabelle, nur von Permutationen ohne andere (bzw. eine well known Verteilung der Permutations-Tupels).
Danke für die Infos, euch beiden.
-
@dugfe sagte in Mögliche Kombinationen erzeugen:
Aber angenommen, die Möglichkeiten sind so begrenzt, dass pro Möglichkeit ein Item auch nur einmal vorkommen darf.
Dann ist das Item auch nur einmal in dem zu permutierendem Dingsti drin.
