std::next_permutation Implementierungserklärung

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

Übersicht ü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 vor 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 i um.

Beispiel

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

• Iteration 1: i ist anfangs bei 3. j ist bei 2. Da 3
• Iteration 2: Es wird festgestellt, dass k 2 ist. 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
• Iteration 4: Es wird festgestellt, dass k 1 ist. 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}.