Byłem ciekawy jakstd:next_permutation został zaimplementowany, więc wyodrębniłemgnu libstdc++ 4.7 wersja i oczyszczono identyfikatory i formatowanie, aby uzyskać 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()));
}

Wynik jest zgodny z oczekiwaniami:http://ideone.com/4nZdx

Moje pytania to: Jak to działa? Jakie jest znaczeniei, j ik? Jaką wartość mają w różnych częściach egzekucji? Jaki jest szkic dowodu jego poprawności?

Oczywiście przed wejściem do głównej pętli po prostu sprawdza trywialne przypadki list elementów 0 lub 1. Przy wejściu do głównej pętli wskazuję na ostatni element (nie jeden koniec), a lista ma co najmniej 2 elementy.

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