std :: next_permutation Implementierung Erläuterung

Ich war neugierig, wie std:next_permutation implementiert wurde, also extrahierte ich die gnu libstdc++ 4.7 Version und bereinigte die Bezeichner und Formatierung, um die folgende Demo zu erzeugen …

 #include  #include  #include  using namespace std; template bool next_permutation(It begin, It end) { if (begin == end) return false; It i = begin; ++i; if (i == end) return false; i = end; --i; while (true) { It j = i; --i; if (*i < *j) { It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true; } if (i == begin) { reverse(begin, end); return false; } } } int main() { vector v = { 1, 2, 3, 4 }; do { for (int i = 0; i < 4; i++) { cout << v[i] << " "; } cout << endl; } while (::next_permutation(v.begin(), v.end())); } 

Die Ausgabe ist wie erwartet: http://ideone.com/4nZdx

Meine Fragen sind: Wie funktioniert es? Was bedeuten i , j und k ? Welchen Wert haben sie an den verschiedenen Ausführungsteilen? Was ist eine Skizze eines Beweises für ihre Richtigkeit?

Vor dem Eintritt in die Hauptschleife überprüft es einfach die trivialen 0 oder 1 Elementlistenfälle. Bei der Eingabe der Hauptschleife zeigt i auf das letzte Element (nicht eins nach dem Ende) und die Liste ist mindestens 2 Elemente lang.

Was passiert im Körper der Hauptschleife?

   

    Lassen Sie uns einige Permutationen betrachten:

     1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 ... 

    Wie gehen wir von einer Permutation zur nächsten? Erstens, lassen Sie uns die Dinge ein wenig anders betrachten. Wir können die Elemente als Ziffern und die Permutationen als Zahlen betrachten . Wenn wir das Problem auf diese Weise betrachten , wollen wir die Permutationen / Zahlen in “aufsteigender” Reihenfolge anordnen .

    Wenn wir Zahlen ordnen, wollen wir sie “um den kleinsten Betrag erhöhen”. Zum Beispiel zählen wir beim Zählen nicht 1, 2, 3, 10, … weil es immer noch 4, 5, … dazwischen gibt und obwohl 10 größer als 3 ist, gibt es fehlende Zahlen, die man bekommen kann 3 um einen kleineren Betrag erhöhen. Im obigen Beispiel sehen wir, dass 1 für eine lange Zeit als die erste Zahl bleibt, da es viele Umordnungen der letzten 3 “Ziffern” gibt, die die Permutation um einen kleineren Betrag “erhöhen”.

    Wann “benutzen” wir dann die 1 ? Wenn es nur noch keine Permutationen der letzten 3 Ziffern gibt.
    Und wann gibt es keine Permutationen der letzten 3 Ziffern? Wenn die letzten 3 Ziffern in absteigender Reihenfolge sind.

    Aha! Dies ist der Schlüssel zum Verständnis des Algorithmus. Wir ändern nur die Position einer “Ziffer”, wenn alles auf der rechten Seite in absteigender Reihenfolge ist, denn wenn es nicht in absteigender Reihenfolge ist, dann gibt es noch mehr Permutationen (dh wir können die Permutation um einen kleineren Betrag “erhöhen”) .

    Gehen wir nun zurück zum Code:

     while (true) { It j = i; --i; if (*i < *j) { // ... } if (i == begin) { // ... } } 

    Von den ersten beiden Zeilen in der Schleife ist j ein Element und i ist das Element davor.
    Wenn die Elemente in aufsteigender Reihenfolge sind, ( if (*i < *j) ), dann tue etwas.
    Andernfalls, wenn das Ganze in absteigender Reihenfolge ist ( if (i == begin) ), ist dies die letzte Permutation.
    Ansonsten gehen wir weiter und wir sehen, dass j und i im Wesentlichen dekrementiert sind.

    Wir verstehen jetzt den if (i == begin) Teil, also müssen wir nur den if (*i < *j) Teil verstehen.

    Beachten Sie auch: "Dann, wenn die Elemente in aufsteigender Reihenfolge sind ...", was unsere vorherige Beobachtung unterstützt, dass wir nur etwas zu einer Ziffer machen müssen, "wenn alles rechts absteigend ist". Die aufsteigende Reihenfolge if statement findet im Wesentlichen den äußersten linken Platz, an dem "alles rechts absteigend ist".

    Schauen wir uns noch einmal einige Beispiele an:

     ... 1 4 3 2 2 1 3 4 ... 2 4 3 1 3 1 2 4 ... 

    Wir sehen, dass, wenn alles rechts von einer Ziffer in absteigender Reihenfolge ist, wir die nächstgrößere Ziffer finden und sie voranstellen und dann die verbleibenden Ziffern in aufsteigender Reihenfolge setzen .

    Schauen wir uns den Code an:

     It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true; 

    Nun, da die Dinge auf der rechten Seite in absteigender Reihenfolge sind, um die "nächstgrößere Ziffer" zu finden, müssen wir nur vom Ende aus iterieren, was wir in den ersten 3 Zeilen des Codes sehen.

    Als nächstes tauschen wir die "nächstgrößere Ziffer" mit der iter_swap() nach vorne, und da wir wissen, dass die Ziffer die nächstgrößere ist, wissen wir, dass die Ziffern rechts immer noch in absteigender Reihenfolge sind, um sie zu setzen aufsteigende Reihenfolge, wir müssen es nur reverse() .

    Die gcc-Implementierung erzeugt Permutationen in lexikographischer Reihenfolge. Wikipedia erklärt es wie folgt:

    Der folgende Algorithmus generiert lexikografisch die nächste Permutation nach einer gegebenen Permutation. Es ändert die gegebene Permutation an Ort und Stelle.

    1. Finde den größten Index k mit a [k]
    2. Finde den größten Index l mit a [k]
    3. Tausche a [k] mit a [l].
    4. Umkehren Sie die Sequenz von [k + 1] bis einschließlich des letzten Elements a [n].

    Knuth geht auf diesen Algorithmus und seine Verallgemeinerungen in den Abschnitten 7.2.1.2 und 7.2.1.3 von The Art of Computer Programming ein . Er nennt es “Algorithmus L” – anscheinend stammt es aus dem 13. Jahrhundert.

    Hier ist eine vollständige Implementierung mit anderen Standard-Bibliotheksalgorithmen:

     template  // requires BidirectionalIterator && Compare bool my_next_permutation(I begin, I end, C comp) { auto rbegin = std::make_reverse_iterator(end); auto rend = std::make_reverse_iterator(begin); auto next_unsorted = std::is_sorted_until(rbegin, rend, comp); bool at_final_permutation = (next_unsorted == rend); if (!at_final_permutation) { auto next_permutation = std::upper_bound( rbegin, next_unsorted, *next_unsorted, comp); std::iter_swap(next_unsorted, next_permutation); } std::reverse(rbegin, next_unsorted); return !at_final_permutation; } 

    Demo

    Es gibt eine selbsterklärende Implementierung bei cppreference mit .

     template  bool next_permutation(Iterator first, Iterator last) { if (first == last) return false; Iterator i = last; if (first == --i) return false; while (1) { Iterator i1 = i, i2; if (*--i < *i1) { i2 = last; while (!(*i < *--i2)); std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i == first) { std::reverse(first, last); return false; } } } 

    Ändern Sie den Inhalt in lexikografisch nächste Permutation (in-place) und geben Sie wahr zurück, wenn vorhanden, andernfalls sort und geben Sie false zurück, wenn es nicht existiert.