std :: next_permutation Objaśnienie implementacji

Byłem ciekawy, jak std:next_permutationzostał zaimplementowany, więc wyodrębniłem gnu libstdc++ 4.7wersję i wyczyściłem identyfikatory i formatowanie, aby utworzyć następujące demo ...

#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()));
}

Dane wyjściowe są zgodne z oczekiwaniami: http://ideone.com/4nZdx

Moje pytania to: jak to działa? Co to ma znaczyć i, ji k? Jaką wartość mają w różnych częściach egzekucji? Czym jest szkic dowodu jego poprawności?

Najwyraźniej przed wejściem do głównej pętli sprawdza tylko trywialne przypadki z listą elementów 0 lub 1. Na wejściu głównej pętli i wskazuje na ostatni element (nie jeden poza koniec), a lista ma co najmniej 2 elementy.

Co się dzieje w głównej pętli?

Spójrzmy na kilka permutacji:

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
...

Jak przechodzimy od jednej permutacji do drugiej? Po pierwsze, spójrzmy na to trochę inaczej. Możemy zobaczyć elementy jako cyfry, a permutacje jako liczby . Patrząc na problem w ten sposób , chcemy uporządkować permutacje / liczby w porządku „rosnącym” .

Zamawiając numery chcemy „zwiększyć je o najmniejszą ilość”. Na przykład podczas liczenia nie liczymy 1, 2, 3, 10, ... ponieważ nadal jest 4, 5, ... pomiędzy i chociaż 10 jest większe niż 3, brakuje liczb, które można uzyskać przez zwiększenie 3 o mniejszą kwotę. W powyższym przykładzie widzimy, że 1pozostaje jako pierwsza liczba przez długi czas, ponieważ istnieje wiele zmian kolejności ostatnich 3 „cyfr”, które „zwiększają” permutację o mniejszą wartość.

Kiedy więc w końcu „używamy” 1? Gdy nie ma już tylko permutacji ostatnich 3 cyfr.
A kiedy nie będzie już permutacji ostatnich 3 cyfr? Gdy ostatnie 3 cyfry są w porządku malejącym.

Aha! To klucz do zrozumienia algorytmu. Zmieniamy pozycję „cyfry” tylko wtedy, gdy wszystko po prawej stronie jest w porządku malejącym, ponieważ jeśli nie jest w porządku malejącym, to jest jeszcze więcej permutacji do przejścia (tj. Możemy „zwiększyć” permutację o mniejszą wartość) .

Wróćmy teraz do kodu:

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

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

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

Od pierwszych 2 wierszy w pętli jjest elementem i ijest elementem przed nim.
Następnie, jeśli elementy są w porządku rosnącym, ( if (*i < *j)) zrób coś.
W przeciwnym razie, jeśli całość jest w porządku malejącym ( if (i == begin)), to jest to ostatnia permutacja.
W przeciwnym razie kontynuujemy i widzimy, że j oraz i są zasadniczo dekrementowane.

Teraz rozumiemy if (i == begin)część, więc wszystko, co musimy zrozumieć, to if (*i < *j)część.

Zwróć również uwagę: „Wtedy, jeśli elementy są w porządku rosnącym…”, co potwierdza naszą poprzednią obserwację, że wystarczy zrobić coś z cyfrą, „gdy wszystko po prawej stronie jest w porządku malejącym”. Wyrażenie w kolejności rosnącej ifzasadniczo polega na znajdowaniu skrajnego lewego miejsca, w którym „wszystko po prawej stronie jest w porządku malejącym”.

Spójrzmy ponownie na kilka przykładów:

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

Widzimy, że gdy wszystko na prawo od cyfry jest w porządku malejącym, znajdujemy następną największą cyfrę i umieszczamy ją na początku, a pozostałe cyfry układamy rosnąco .

Spójrzmy na kod:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Cóż, ponieważ elementy po prawej stronie są w porządku malejącym, aby znaleźć „następną największą cyfrę”, musimy po prostu powtórzyć iterację od końca, co widzimy w pierwszych 3 wierszach kodu.

Następnie zamieniamy „następną największą cyfrę” na początek iter_swap()stwierdzeniem, a ponieważ wiemy, że ta cyfra była następną co do wielkości, wiemy, że cyfry po prawej stronie są nadal w porządku malejącym, więc ustawimy je w porządku rosnącym, po prostu musimy to reverse()zrobić.

Implementacja gcc generuje permutacje w porządku leksykograficznym. Wikipedia wyjaśnia to następująco:

Poniższy algorytm generuje leksykograficznie następną permutację po danej permutacji. Zmienia daną permutację w miejscu.

1. Znajdź największy indeks k taki, że a [k] <a [k + 1]. Jeśli taki indeks nie istnieje, permutacja jest ostatnią permutacją.
2. Znajdź największy indeks l taki, że a [k] <a [l]. Ponieważ k + 1 jest takim indeksem, l jest dobrze zdefiniowane i spełnia k <l.
3. Zamień [k] na [l].
4. Odwróć sekwencję od a [k + 1] do ostatniego elementu a [n] włącznie.

Knuth szczegółowo omawia ten algorytm i jego uogólnienia w sekcjach 7.2.1.2 i 7.2.1.3 książki The Art of Computer Programming . Nazywa go „Algorytmem L” - podobno pochodzi z XIII wieku.

Oto pełna implementacja przy użyciu innych standardowych algorytmów bibliotecznych:

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;
}

Próbny

Istnieje oczywista możliwa implikacja dotycząca używania cppreference<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;
        }
    }
}

Zmień zawartość na następną permutację leksykograficzną (lokalną) i zwróć wartość true, jeśli istnieje, w przeciwnym razie sortuj i zwróć false, jeśli nie istnieje.