Wie funktioniert der Algorithmus std::next_permutation, um die nächstgrößere Permutation einer Sequenz zu finden?

std::next_permutation Implementierungserklärung

Der std::next_permutation-Algorithmus berechnet die nächstgrößere lexikographisch größere Permutation einer gegebenen Sequenz. Das Verständnis seiner Implementierung ist entscheidend für das Verständnis seines Verhaltens.

Überblick über den Algorithmus

Der Algorithmus iteriert über die Sequenz von rechts nach links und sucht nach dem „Aufsteiger“ ganz links (d. h. , ein Element, das kleiner als sein Nachfolger ist). Wenn keine Oberlänge gefunden wird, bedeutet dies, dass die Reihenfolge in absteigender Reihenfolge vorliegt. In diesem Fall wird die Reihenfolge umgekehrt, um die kleinste Permutation zu erhalten.

Andernfalls fährt der Algorithmus damit fort, das kleinste Element in der Reihenfolge rechts zu finden der Oberlänge (genannt „k“). Dieses Element wird dann mit der Oberlänge getauscht. Schließlich werden die Elemente rechts von der Oberlänge umgekehrt, um die absteigende Reihenfolge beizubehalten.

Variable Rollen

• i: Zeigt auf das aktuell untersuchte Element.
• j: Zeigt auf das Element unmittelbar davor i.
• k:Zeigt auf das kleinste Element in der Sequenz rechts von i, wenn i eine Oberlänge ist.

Schleifenfluss

Die Schleife wird wiederholt, bis ich den Anfang der Sequenz erreicht (begin). Innerhalb jeder Iteration:

1. Wenn i keine Oberlänge ist, werden i und j dekrementiert.
2. Wenn i eine Oberlänge ist, wird das kleinste Element rechts von i (k) gefunden ), vertauscht es mit i und kehrt alles rechts von um i.

Beispiel

Betrachten Sie die Sequenz {1, 2, 4, 3}.

• Iteration 1: i ist zunächst bei 3. j ist bei 2. Da 3 < 4 (i < j), i ist eine Oberlänge.
• Iteration 2: k wird als 2 ermittelt. 3 wird mit 2 vertauscht. {1, 3, 4, 2} . Die Elemente rechts von 3 (4 und 2) sind vertauscht. {1, 3, 2, 4}.
• Iteration 3: i wird dekrementiert und j wird dekrementiert. i ist jetzt bei 2. j ist bei 1. 2 < 3, also ist i ein Aufsteiger.
• Iteration 4: k wird als 1 ermittelt. 2 wird mit 1 vertauscht. {1, 2, 4, 3}. Die Elemente rechts von 2 (4 und 3) sind vertauscht. {1, 2, 3, 4}.
• Iteration 5: i wird dekrementiert und j wird dekrementiert. i ist jetzt bei 1. j steht am Anfang der Sequenz. Da keine Oberlängen mehr vorhanden sind, ist die Reihenfolge umgekehrt. {4, 3, 2, 1}.

Das obige ist der detaillierte Inhalt vonWie funktioniert der Algorithmus std::next_permutation, um die nächstgrößere Permutation einer Sequenz zu finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!