Zum Beispiel gibt es 6 Stühle im Raum und es gibt 4 Mädchen und 2 Jungen. Es gibt 15 einzigartige Möglichkeiten, wie sie auf diesem Stuhl sitzen können 6!/(4!*2!)=15 .
Mein Problem ist es, einen effizienten Weg zu finden, die Position der Möglichkeit zu berechnen, die sie wählen, um zu sitzen. Mit Position meine ich folgendes:
%Vor% Zum Beispiel wählen sie die Position GBBGGG ... Vorläufig ist meine Lösung, die Nummer dieser Position zu berechnen (# 6), alle möglichen Positionen zu wiederholen und jede von ihnen mit der ausgewählten Reihenfolge zu vergleichen und die aktuelle Positionsnummer zurückzugeben gleich.
In diesem Bereich von Beispiel oben ist es keine große Sache, 15 mögliche Kombinationen zu wiederholen, aber wenn Sie die Anzahl der Stühle und Personen erhöhen, ist diese Methode bei weitem nicht effizient.
Gibt es eine Formel oder einen effizienteren Weg, um die Position der ausgewählten Möglichkeit zu bestimmen? Fühlen Sie sich frei, irgendeine Programmiersprache in Ihren Beispielen zu benutzen.
UPDATE : Ich weiß genau, wie viele Stühle, Jungs und Mädels im Raum sind. Das einzige Problem besteht darin, die Positionsnummer der Möglichkeit zu finden, die sie wählen, um zu sitzen.
Die Sortierung, die ich in meinem Beispiel verwende, dient nur zur besseren Lesbarkeit. Antworten mit jeder Art von Sortierung sind willkommen.
Den Rang einer Permutation anhand der Position von Gs finden
Die Permutationen im Beispiel sind in lexikographischer Reihenfolge ; die erste Permutation hat alle B's auf der linken und die G's auf der rechten Seite; die anderen Permutationen werden durch allmähliches Verschieben von G nach links gemacht. (Ähnlich einer steigenden Folge von Binärzahlen: 0011, 0101, 0110, 1001, 1010, 1100)
Um zu sehen, wie weit in diesen Prozess eine gegebene Permutation hineinreicht, sehen Sie sich die Zeichen nacheinander von links nach rechts an: Wann immer Sie auf ein G treffen, ist die Anzahl der Permutationen, die Sie benötigen, um N zu bewegen ist die Anzahl der Positionen rechts von der aktuellen Position, und K ist die Anzahl der links von G, einschließlich des aktuellen G.
123456 ← Positionen
BBGGGG ← Rang 0 (oder 1)
BGBGGG ← Rang 1 (oder 2)
BGGBGG ← Rang 2 (oder 3)
BGGGBG ← Rang 3 (oder 4)
BGGGGB ← Rang 4 (oder 5)
GBBGGG ← Rang 5 (oder 6)
GBGBGG ← Rang 6 (oder 7) < br> GBGGBG ← Rang 7 (oder 8)
z. Für GBGGBG in deinem Beispiel gibt es 4 G's in 6 möglichen Positionen und das erste G ist auf Position 1, also zählen wir (6-1 wähle 4) = 5; das zweite G ist an Position 3, also fügen wir hinzu (6-3 wähle 3) = 1; das dritte G ist auf Position 4, also fügen wir hinzu (6-4 wähle 2) = 1; das letzte G befindet sich auf Position 6, also befindet es sich in seiner ursprünglichen Position und kann ignoriert werden. Dies addiert sich zu 7, was bedeutet, dass die Permutation Rang 7 hat (oder 8, wenn Sie von 1 zu zählen beginnen, wie Sie es in der Frage tun).
Berechnen (N wählen Sie K) mit Pascal's Triangle
Sie können z.B. Pascal's Triangle um zu berechnen (N wähle K). Dies ist ein dreieckiges Array, bei dem jede Zahl die Summe der zwei darüber liegenden Zahlen ist:
%Vor%Codebeispiel
Im Folgenden finden Sie eine einfache Javascript-Implementierung. Führen Sie das Code-Snippet aus, um einige Beispiele zu sehen. Die Ausführungszeit ist linear zur Anzahl der Stühle, nicht zur Anzahl der möglichen Permutationen, die sehr groß sein können. (update: Der Code iteriert nun die Zeichen von rechts nach links, so dass er nicht zuerst die Anzahl der G zählen muss.)
Inverse Algorithmus: Permutation erzeugen
Dieser Algorithmus wird das Umgekehrte tun: Angesichts der Anzahl der B's, der Anzahl der G's und des Rangs der Permutation wird die Permutation zurückgegeben. Dies geschieht wiederum, ohne dass alle Permutationen erzeugt werden müssen. (Hinweis: Ich habe keine Überprüfung der Gültigkeit der Eingabe enthalten)
Mein Problem ist es, einen effizienten Weg zu finden, die Position der Möglichkeit zu berechnen, die sie wählen, um zu sitzen. Antworten mit jeder Art von Sortierung sind willkommen. Gibt es eine Formel oder einen effizienteren Weg, um die Position der ausgewählten Möglichkeit zu bestimmen?
Ich wähle das Mapping der Konfiguration auf binary: B ist 1 und G ist 0 .
Für 7 Jungen und 3 Mädchen gibt es 10!/(7! 3!) = 120 Kombinationen, hier sind einige Kombinationen:
Sie können auch in Dezimalzahlen umwandeln, aber in jedem Fall ist es ein 1: 1-Mapping, mit dem Sie die Position fast sofort bestimmen können.
Hier ist ein O (n) effizienter Algorithmus. Kein Pascal-Dreieck - es berechnet die Kombinationen im laufenden Betrieb. Ich habe gegen große Werte getestet, die Kombinationen generiert und die Ränge angepasst, aber wenn Sie ein Beispiel finden, dass es nicht funktioniert, lassen Sie es mich wissen.
Ich würde empfehlen, einen binären Suchbaum zu verwenden. Jedes Mal, wenn Sie einen Stuhl hinzufügen, wird jede Seite des Baumes geklont und die neue Wahl von B oder G wird der einzige Unterschied sein. Grundsätzlich klonen Sie, was Sie haben, und fügen Sie B oder G zu jedem Eintrag auf der Seite hinzu.
EDIT: Beachten Sie, dass dies auch für eine LogN-Suche der Positionierung verwendet werden kann.
Verzweigung und Grenze (BB oder B & amp; B) ist ein Algorithmusentwurfsparadigma für diskrete und kombinatorische Optimierungsprobleme sowie für allgemein reell bewertete Probleme. Ein Branch-and-Bound-Algorithmus besteht aus einer systematischen Aufzählung von Kandidatenlösungen mittels Zustandsraumsuche: Die Menge der Kandidatenlösungen wird als ein verwurzelter Baum mit der vollständigen Menge an der Wurzel betrachtet. Der Algorithmus untersucht Zweige dieses Baums, die Teilmengen des Lösungssatzes darstellen. Bevor die Kandidatenlösungen einer Verzweigung aufgelistet werden, wird die Verzweigung gegen obere und untere geschätzte Grenzen der optimalen Lösung geprüft und verworfen, wenn sie keine bessere Lösung als die bisher beste Lösung des Algorithmus liefern kann.
Der Kern des Branch-and-Bound-Ansatzes ist die folgende Beobachtung: Wenn ich im gesamten Enumerationsbaum an jedem Knoten zeigen kann, dass die optimale Lösung in keinem seiner Nachkommen vorkommen kann, besteht keine Notwendigkeit dafür ich, diese absteigenden Knoten zu betrachten. Daher kann ich den Baum an diesem Knoten "beschneiden". Wenn ich auf diese Weise genug Äste des Baumes beschneiden kann, kann ich es vielleicht auf eine rechnerisch überschaubare Größe reduzieren. Beachten Sie, dass ich diese Lösungen in den Blättern der Zweige, die ich beschnitten habe, nicht ignoriere. Ich habe sie außer Betracht gelassen, nachdem ich sichergestellt habe, dass die optimale Lösung an keinem dieser Knoten sein kann. Daher ist der Branch-and-Bound-Ansatz keine heuristische oder approximierende Prozedur, sondern eine exakte, optimierende Prozedur, die eine optimale Lösung findet.
Tags und Links algorithm language-agnostic math permutation combinatorics