Eu estava curioso comostd:next_permutation foi implementado então eu extraí oognu libstdc++ 4.7 versão e sanitized os identificadores e formatação para produzir o seguinte 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()));
}

A saída é como esperada:http://ideone.com/4nZdx

Minhas perguntas são: Como isso funciona? Qual é o significado dei, j ek? Que valor eles têm nas diferentes partes da execução? O que é um esboço de uma prova de sua correção?

Claramente, antes de entrar no loop principal, ele apenas verifica os casos triviais da lista de elementos 0 ou 1. Na entrada do loop principal, eu estou apontando para o último elemento (não um final passado) e a lista tem pelo menos dois elementos de comprimento.

O que está acontecendo no corpo do loop principal?