Wie findet std::next_permutation die nächste lexikografisch größere Permutation?

So funktioniert std::next_permutation

std::next_permutation ist eine Funktion in der C Standard Template Library (STL), die eine Sequenz neu anordnet in die nächste lexikographisch größere Permutation. Um seine Implementierung zu verstehen, ist es hilfreich, die Sequenz als Zahl zu visualisieren, bei der jedes Element eine Ziffer darstellt.

Kernlogik

Der Algorithmus arbeitet nach den folgenden Prinzipien:

• Finden Sie den Drehpunkt: Beginnend am Ende der Sequenz wird das erste Element (i) lokalisiert, das kleiner ist als das Element rechts davon (j). Dies zeigt an, dass die Ziffern rechts von i in absteigender Reihenfolge sind.
• Vertauschen und umkehren: Sobald i gefunden wurde, wird vom Ende nach dem ersten Element (k) gesucht größer als ich. Dieses Element wird mit i vertauscht und an der Vorderseite platziert. Die verbleibenden Elemente rechts von j (von j bis zum Ende) werden dann umgekehrt.
• Pivot erhöhen: Wenn ein Pivot gefunden wird (i ist nicht der Anfang), wiederholt sich der Vorgang durch Dekrementieren von i und j.
• Umkehren und beenden: Wenn kein Pivot gefunden werden kann (i ist der Anfang), wird die Sequenz umgekehrt und die Funktion gibt „false“ zurück, was anzeigt, dass keine Permutationen mehr vorhanden sind sind möglich.

Variablen im Code

• i: Stellt das Pivotelement ganz links dar.
• j: Stellt das Element rechts von i dar, das kleiner als i ist.
• k: Stellt das Element rechts von i dar, das größer als i und will ist mit i vertauscht werden.

Beispiel

Betrachten Sie die Reihenfolge: 1, 3, 2, 4.

• Finden Sie den Pivot: i ist zunächst auf 4 gesetzt, aber da 4 größer oder gleich 2 ist, gehen wir zu i = 2. Da 2 kleiner als 4 ist, ist i der Pivot.
• Swap and Reverse: j wird auf 3 und k auf 1 gesetzt, was das erste Element von rechts ist, das größer als 2 ist. 1 wird mit 2 vertauscht, was zu 1, 2, 3 führt , 4. Die verbleibenden Elemente von j bis zum Ende (2, 3, 4) werden umgekehrt, was 1, 2, 4, 3 ergibt.
• Pivot erhöhen: i wird auf 1 dekrementiert (j ist bereits auf 2 gesetzt). Da 1 kleiner als 2 ist, wird der Vorgang wiederholt.
• Pivot finden: i wird auf das erste Element (Anfang) dekrementiert, was anzeigt, dass kein Pivot gefunden werden kann.
• Umkehren und Beenden: Die Sequenz wird in ihren ursprünglichen Zustand 1, 2, 3, 4 umgekehrt und die Funktion gibt „false“ zurück, was anzeigt, dass keine Permutationen mehr möglich sind.

Das obige ist der detaillierte Inhalt vonWie findet std::next_permutation die nächste lexikografisch größere Permutation?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!