std::next_permutation Implementation Explanation

Question

I was curious how std:next_permutation was implemented so I extracted the the gnu libstdc++ 4.7 version and sanitized the identifiers and formatting to produce the following 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()));
}

The output is as expected: http://ideone.com/4nZdx

My questions are: How does it work? What is the meaning of i, j and k? What value do they hold at the different parts of execution? What is a sketch of a proof of its correctness?

Clearly before entering the main loop it just checks the trivial 0 or 1 element list cases. At entry of the main loop i is pointing to the last element (not one past end) and the list is at least 2 elements long.

What is going on in the body of the main loop?

Answer 1

Let's look at some permutations:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...

How do we go from one permutation to the next? Firstly, let's look at things a little differently. We can view the elements as digits and the permutations as numbers. Viewing the problem in this way we want to order the permutations/numbers in "ascending" order.

When we order numbers we want to "increase them by the smallest amount". For example when counting we don't count 1, 2, 3, 10, ... because there are still 4, 5, ... in between and although 10 is larger than 3, there are missing numbers which can be gotten by increasing 3 by a smaller amount. In the example above we see that 1 stays as the first number for a long time as there are many reorderings of the last 3 "digits" which "increase" the permutation by a smaller amount.

So when do we finally "use" the 1? When there are only no more permutations of the last 3 digits.
And when are there no more permutations of the last 3 digits? When the last 3 digits are in descending order.

Aha! This is key to understanding the algorithm. We only change the position of a "digit" when everything to the right is in descending order because if it isn't in descending order then there are still more permutations to go (ie we can "increase" the permutation by a smaller amount).

Let's now go back to the code:

while (true)
{
    It j = i;
    --i;

    if (*i < *j)
    { // ...
    }

    if (i == begin)
    { // ...
    }
}

From the first 2 lines in the loop, j is an element and i is the element before it.
Then, if the elements are in ascending order, (if (*i < *j)) do something.
Otherwise, if the whole thing is in descending order, (if (i == begin)) then this is the last permutation.
Otherwise, we continue and we see that j and i are essentially decremented.

We now understand the if (i == begin) part so all we need to understand is the if (*i < *j) part.

Also note: "Then if the elements are in ascending order ..." which supports our previous observation that we only need to do something to a digit "when everything to the right is in descending order". The ascending order if statement is essentially finding the leftmost place where "everything to the right is in descending order".

Let's look again at some examples:

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

We see that when everything to the right of a digit is in descending order, we find the next largest digit and put it in front and then put the remaining digits in ascending order.

Let's look at the code:

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

Well, since the things to the right are in descending order, to find the "next largest digit" we just have to iterate from the end, which we see in the first 3 lines of code.

Next, we swap the "next largest digit" to the front with the iter_swap() statement and then since we know that digit was the next largest, we know that the digits to the right are still in descending order, so to put it in ascending order, we just have to reverse() it.