Std :: next_permutation implementation explanation

Question

I was curious how std:next_permutation was implemented, so I extracted the gnu libstdc++ 4.7 version of gnu libstdc++ 4.7 and sanitized the identifiers and formatting to create the next 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 executed 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 play in different parts of the performance? What is a sketch of proof of its correctness?

It is clear that before entering the main loop, he simply checks the trivial cases of the list of elements 0 or 1. When entering the main loop, I indicate the last element (and not one end), and the list has a length of at least 2 elements.

What happens 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 move from one permutation to the next? First, let's look at things a little differently. We can consider elements as numbers and permutations as numbers . Looking at the problem this way , we want to order the permutations / numbers in ascending order .

When we order rooms, we want to "increase them by the minimum amount." For example, when counting, we do not take into account 1, 2, 3, 10, ... because there are 4, 5, ... between them and although 10 is greater than 3, there are no numbers that can be obtained by increasing 3 by a smaller amount. In the above example, we see that 1 remains as the first number for a long time, since there are many reorders of the last 3 “digits” that “increase” the permutation by a smaller amount.

So, when do we finally “use” 1 ? When there is no only permutation of the last three digits.
And when there are no more permutations from the last three digits? When the last 3 digits are in descending order.

Yeah! This is the key to understanding the algorithm. We only change the position of the “figure” when everything on the right is in descending order , because if it is not in descending order, there are even more permutations (that is, we can “increase”, the permutation by a smaller amount).

Now back to the code:

 while (true) { It j = i; --i; if (*i < *j) { // ... } if (i == begin) { // ... } } 

Of the first two lines in the loop, j is the element, and i is the element in front of it.
Then, if the elements are in ascending order, ( if (*i < *j) ) do something.
Otherwise, if all this is in decreasing order, ( if (i == begin) ), then this is the last permutation.
Otherwise, we continue and see that j and i are substantially reduced.

Now we understand the if (i == begin) , so all we need to understand is the if (*i < *j) .

Also note: “Then, if the elements are in ascending order ...”, which supports our previous observation, we only need to do the figure “when everything is in order in descending order”. The upstream operator if essentially finds the leftmost place, where "everything on 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 the number is in descending order, we find the next big number and put it in front , and then put the remaining numbers in ascending order .

Take a look at the code:

 It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true; 

Well, since the things on the right are in descending order to find the “next big digit”, we just need to iterate from the end, which we see in the first three lines of code.

Then we replace the “next largest digit” with a iter_swap() operator, and then, since we know that the digit was the next largest, we know that the numbers on the right are still in descending order, so put it in ascending order, we just need reverse() it.

Answer 2

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

The following algorithm generates the next permutation lexicographically after this permutation. It modifies the given permutation in place.

• Find the largest index k such that a [k] a [k + 1]. If no such index exists, the permutation is the last permutation.
• 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.
• Change a [k] to [l].
• Cancel the sequence from [k + 1] to the final element a and include it in [n].

Answer 3

Knut describes this algorithm more deeply and its generalizations in sections 7.2.1.2 and 7.2.1.3, "The Art of Computer Programming." He calls it the "Algorithm L" - apparently, this refers to the XIII century.

Answer 4

Here's the full implementation using other standard library algorithms:

 template <typename I, typename C> // requires BidirectionalIterator<I> && StrictWeakOrdering<C, ValueType<I>> 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 sorted_end = std::is_sorted_until(rbegin, rend, comp); bool has_greater_permutation = (sorted_end != rend); if (has_greater_permutation) { std::iter_swap( sorted_end, std::upper_bound(rbegin, sorted_end, *sorted_end, comp)); } std::reverse(rbegin, sorted_end); return has_greater_permutation; } template <typename I> // requires BidirectionalIterator<I> && TotallyOrdered<ValueType<I>> bool my_next_permutation(I begin, I end) { return my_next_permutation( begin, end, std::less<typename std::iterator_traits<I>::value_type>{}); } 

Demo

Answer 5

There is a self-evident possible implementation 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 the next lexicographically permutation (in place) and return true if sorting exists otherwise and return false if it does not exist.