How to find next permutation
This is introduce how to find the next lexicographically permutation.
Suppose the permutation is 1 2 3
. The next one is 1 3 2
.
Algorithm in C++
C++ provide an algorithm called next_permutation
to support that. Reference
Example:
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort
int main () {
int myints[] = {1,2,3};
std::sort (myints,myints+3);
std::cout << "The 3! possible permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while ( std::next_permutation(myints,myints+3) );
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
return 0;
How it work.
There are four step to achieve.
- Find first decreasing element
A
in backward. - Find element
B
behindA
and just large thenA
. - Swap
A
andB
. - Reverse all elements behind
B
.
Why it works
Example each step
- Find the element that should be changed.
- Find the next element that will replace the previous one.
- Swap them.
- Since all elements behind the new one is decreasing, reverse them.