std :: next_permutation Implementierungserklärung

Ich war neugierig, wie std:next_permutationes implementiert wurde, also extrahierte ich die gnu libstdc++ 4.7Version und bereinigte die Bezeichner und Formatierungen, um die folgende Demo zu erstellen ...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
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<int> 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 ist der Sinn i, jund k? Welchen Wert haben sie für die verschiedenen Teile der Ausführung? Was ist eine Skizze eines Beweises für seine Richtigkeit?

Es ist klar, dass vor dem Eintritt in die Hauptschleife nur die trivialen 0- oder 1-Elementlistenfälle überprüft werden. Beim Eintritt in die Hauptschleife zeigt i auf das letzte Element (nicht auf ein hinteres Ende) und die Liste ist mindestens 2 Elemente lang.

Was ist im Körper der Hauptschleife los?

Schauen wir uns einige Permutationen an:

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? Lassen Sie uns zunächst die Dinge etwas anders betrachten. Wir können die Elemente als Ziffern und die Permutationen als Zahlen betrachten . Wenn wir das Problem auf diese Weise betrachten , möchten wir die Permutationen / Zahlen in "aufsteigender" Reihenfolge sortieren .

Wenn wir Nummern bestellen, wollen wir sie "um den kleinsten Betrag erhöhen". Zum Beispiel zählen wir beim Zählen nicht 1, 2, 3, 10, ... weil immer noch 4, 5, ... dazwischen liegen und obwohl 10 größer als 3 ist, fehlen Zahlen, die man abrufen kann 3 um einen kleineren Betrag erhöhen. Im obigen Beispiel sehen wir, dass dies 1lange Zeit die erste Zahl bleibt, da es viele Neuordnungen der letzten 3 "Ziffern" gibt, die die Permutation um einen kleineren Betrag "erhöhen".

Wann "benutzen" wir endlich das 1? Wenn nur noch keine Permutationen der letzten 3 Ziffern mehr vorhanden sind.
Und wann gibt es keine Permutationen mehr 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 die Position einer "Ziffer" nur, wenn alles rechts in absteigender Reihenfolge ist, denn wenn es nicht in absteigender Reihenfolge ist, sind noch mehr Permutationen übrig (dh wir können die Permutation um einen kleineren Betrag "erhöhen"). .

Kehren wir nun zum Code zurück:

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

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

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

Von den ersten 2 Zeilen in der Schleife jist ein Element und iist das Element davor.
Wenn die Elemente in aufsteigender Reihenfolge sind, ( if (*i < *j)) tun Sie etwas.
Andernfalls ist if (i == begin)dies die letzte Permutation , wenn das Ganze in absteigender Reihenfolge ( ) ist.
Ansonsten fahren wir fort und 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 stützt, dass wir nur etwas mit einer Ziffer tun müssen, "wenn alles rechts in absteigender Reihenfolge ist". Die Anweisung in aufsteigender Reihenfolge iffindet im Wesentlichen die Stelle ganz links, an der "alles rechts in absteigender Reihenfolge" 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 vor 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, müssen wir nur vom Ende an iterieren, um die "nächstgrößere Ziffer" zu finden, die wir in den ersten drei Codezeilen sehen.

Als nächstes tauschen wir die "nächstgrößere Ziffer" mit der iter_swap()Anweisung nach vorne und da wir wissen, dass diese Ziffer die nächstgrößere war, wissen wir, dass die Ziffern rechts immer noch in absteigender Reihenfolge sind, um sie in aufsteigender Reihenfolge anzuordnen. wir müssen reverse()es einfach tun .

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

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

1. Finden Sie den größten Index k so, dass a [k] <a [k + 1] ist. Wenn kein solcher Index vorhanden ist, ist die Permutation die letzte Permutation.
2. Finden Sie den größten Index l so, dass a [k] <a [l] ist. Da k + 1 ein solcher Index ist, ist l gut definiert und erfüllt k <l.
3. Tausche a [k] gegen a [l].
4. Kehren Sie die Reihenfolge von a [k + 1] bis einschließlich des letzten Elements a [n] um.

Knuth geht in den Abschnitten 7.2.1.2 und 7.2.1.3 der Kunst der Computerprogrammierung ausführlich auf diesen Algorithmus und seine Verallgemeinerungen ein . Er nennt es "Algorithmus L" - anscheinend stammt es aus dem 13. Jahrhundert.

Hier ist eine vollständige Implementierung unter Verwendung anderer Standardbibliotheksalgorithmen:

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
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 rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;
    if (has_more_permutations) {
        auto next_permutation_rend = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, next_permutation_rend);
    }
    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Demo

Es gibt eine selbsterklärende mögliche Implemetation auf cppreference using <algorithm>.

template <class Iterator>
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 die lexikografisch nächste Permutation (an Ort und Stelle) und geben Sie true zurück, falls vorhanden. Andernfalls sortieren Sie false und geben false zurück, wenn es nicht vorhanden ist.