std next permutation Implementation Explanation

Question

I was intrigued about how std:next permutation worked, so I pulled the gnu libstdc++ 4.7 version and cleaned the IDs and formatting to create the following sample.

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

My inquiries are as follows: How does it work? 

What do the letters I j, and k mean? 

What importance do they place on the various stages of execution? 

What is an evidence of its accuracy sketch?

Clearly, it just examines the trivial 0 or 1 element list situations before entering the main loop. 

I am pointing to the final element (not one past the end) at the start of the main loop, and the list is at least two elements long.

What is going on in the main loop's body?

Answer 1

Permutations are generated in lexicographical order by the gcc implementation.

According to Wikipedia, it is as follows:

After a given permutation, the following procedure creates the next permutation lexicographically.

It modifies the current permutation.

1. Determine the highest index k for which a[k] = a[k + 1]. The permutation is the latest permutation if no such index exists.

2. Determine the highest index l for which a[k] = a[l].

l is properly defined and fulfils k l since k + 1 is such an index.

3. Swap a[k] to a[l].

4. Reverse the sequence, starting with a[k + 1] and ending with a[n].