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

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

Результат такой, как и ожидалось:http://ideone.com/4nZdx

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

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

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