std ::next _перестановка Объяснение реализации

Мне было любопытно, как реализован std:next_permutation, поэтому я извлек версию gnu libstdc++ 4.7и очистил идентификаторы и форматирование, чтобы создать следующую демонстрацию...

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

Вывод соответствует ожиданиям:http://ideone.com/4nZdx

Мои вопросы: :Как это работает? Что означают i, jи k? Какую ценность они имеют на разных этапах исполнения? Что такое набросок доказательства его правильности?

Очевидно, что перед входом в основной цикл он просто проверяет тривиальные случаи списка 0 или 1 элемента. При входе в основной цикл я указывает на последний элемент (, а не на один прошлый конец ), и список состоит как минимум из 2 элементов.

Что происходит в теле основного цикла?