std::next_permutation Implementation Explanation

user_1131467 0
Viewed 33612

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?

lexicographic permutation c++11 stl-algorithm c++
6 Answers
#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;
}
user_78081510
Related