Wie funktioniert der Algorithmus „std::next_permutation' und was stellen die Variablen „i', „j' und „k' dar?

std::next_permutation Implementation Explanation

Frage:

Wie funktioniert das std::next_permutation Algorithmus funktioniert? Was stellen die Variablen i, j und k dar und wie ändern sich ihre Werte während der Ausführung?

Verstehen der Konzept:

Um std::next_permutation zu verstehen, können wir Permutationen als Zahlen betrachten, deren Ziffern durch Elemente dargestellt werden. Das Ziel besteht darin, die nächste Permutation in „aufsteigender“ Reihenfolge zu generieren und so den Betrag zu minimieren, um den sich die Zahl erhöht.

Die Kernschleife:

Das Herzstück der Der Algorithmus liegt in einer While-Schleife:

while (true) {
    It j = i;
    --i;

    if (*i < *j) {
        // ...
    }

    if (i == begin) {
        // ...
    }
}

Diese Schleife iteriert rückwärts vom letzten Element zum ersten. Die wichtigste Erkenntnis ist, dass wir die Position einer Ziffer nur ändern müssen, wenn alles rechts in absteigender Reihenfolge ist.

Die am weitesten links stehende absteigende Reihenfolge finden:

Wenn Die Elemente, auf die i und j zeigen, sind in aufsteigender Reihenfolge. Wir haben die am weitesten links stehende absteigende Reihenfolge gefunden.

Austauschen und Neuanordnen:

Wenn wir die am weitesten links stehende absteigende Folge finden, tauschen wir die Ziffer, auf die i zeigt, mit der „nächstgrößten“ Ziffer rechts davon aus. Diese Ziffer wird identifiziert, indem wir vom Ende aus iterieren und anhalten, wenn wir eine Ziffer größer als i finden.

Nach dem Austausch sind die verbleibenden Ziffern rechts bereits in absteigender Reihenfolge, also einfach Kehren Sie sie um, um die nächste Permutation zu erhalten.

Spezifische Variablen:

• i: Zeiger auf das Element ganz links in der absteigenden Sequenz.
• j: Zeiger auf das Element rechts von i.
• k: Zeiger auf das Element zum rechts von i, das unmittelbar größer ist als i.

Das obige ist der detaillierte Inhalt vonWie funktioniert der Algorithmus „std::next_permutation' und was stellen die Variablen „i', „j' und „k' dar?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!