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?

Munsey

Hey how did you extract that piece of code? When i checked #include <algorithm>, the code was completely different which consisted of more functions – Sweepstakes

I just noticed that there no return clause at the bottom of that function, is this a good practice? Why dont it return false? – Mcmaster

@Jeff: The while (true) statement is an infinite loop, the function only returns via the inner return statements the loop encloses. – Munsey

@Sweepstakes Here, it is the same: github.com/gcc-mirror/gcc/blob/… – Irritability

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.

Eufemiaeugen

Thanks for explanation! This algorithm is called Generation in lexicographic order. There are numbers of such algorithm in Combinatorics, but this is the most classical one. – Meteor

What is the complexity of such algorithm? – Mistranslate

leetcode has good explanation, leetcode.com/problems/next-permutation/solution – Stringhalt

I thought i would need a Youtube video to understand it. But the explanation is so good... I just went through it once and I needn't read it again(nor a yt video). superb explanation!!! – Sy

techiedelight.com/std_next_permutation-overview-implementation – Tripletail

Answer 2

The gcc implementation generates permutations in lexicographical order. Wikipedia explains it as follows:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

Thomasenathomasin

AFAICT, all implementations generate the same order. – Directorate

Answer 3

Knuth goes into depth about this algorithm and its generalizations in sections 7.2.1.2 and 7.2.1.3 of The Art of Computer Programming. He calls it "Algorithm L" -- apparently it dates back to the 13th century.

Antitype

Can you please mention the name of the book? – Gaskill

TAOCP = The Art of Computer Programming – Antitype

Answer 4

Here's a complete implementation using other standard library algorithms:

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;

    if (has_more_permutations) {
        auto rupper_bound = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, rupper_bound);
    }

    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

Demo

Vogler

This underscores the importance of good variable names and separation of concerns. is_final_permutation is more informative than begin == end - 1. Calling is_sorted_until/upper_bound separates the permutation logic from those operations, and makes this far more understandable. Additionally upper_bound is a binary search, while while (!(*i < *--k)); is linear, so this is more performant. – Hovis

@JonathanGawrych The complexity is better but not necessarily more performant in real practice. – Penance

Answer 5

There is a self explanatory possible implemetation on cppreference using <algorithm>.

template <class Iterator>
bool next_permutation(Iterator first, Iterator last) {
    if (first == last) return false;
    Iterator i = last;
    if (first == --i) return false;
    while (1) {
        Iterator i1 = i, i2;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2));
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Change the content to lexicographically next permutation (in-place) and return true if exists otherwise sort and return false if it doesn't exist.

Selfexamination

Answer 6

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {

    int int_array_11[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
    do {
        copy(begin(int_array_11), end(int_array_11), ostream_iterator<int>(cout, " "));
        cout << endl;
    } while (next_permutation(begin(int_array_11), end(int_array_11)));

    return 0;
}

Flasket