std::next_permutation | Overview and Implementation in C++

This post discusses std::next_permutation, which can be used to find the lexicographically greater permutations of a string.

The lexicographic or lexicographical order (aka lexical order, dictionary order, alphabetical order) means that the words are arranged as they are presumed to appear in a dictionary. For example, the next permutation in lexicographic order for string 123 is 132.

The STL provides std::next_permutation, which returns the next permutation in lexicographic order by in-place rearranging the specified object as a lexicographically greater permutation. The function returns true if the next higher permutation exists; otherwise, it returns false to indicate that the object is already at the highest possible permutation and reset the range according to the first permutation.

std::next_permutation generates the next permutation in just linear time, and it can also handle repeated characters and generates distinct permutations. Its usage can be seen below:

#include <iostream>

#include <algorithm>

int main()

{

std::string s = "231";

/* Optional: sort the string in a natural order before calling

std::next_permutation inside a loop to print all permutations,

not just the ones that follow specified string lexicographically */

// std::sort(begin(s), end(s));

// find all lexicographically greater permutations using

// std::next_permutation

while (1)

{

// print the current permutation

std::cout << s << " ";

// find the next permutation in lexicographic order

if (!std::next_permutation(begin(s), end(s))) {

break;

}

return 0;

}

Download Run Code

Output:

231 312 321

We can also implement our next_permutation method. The following in-place algorithm lexicographically generates the next permutation after a given permutation:

Find the largest index i such that s[i-1] is less than s[i].
If i is the first index of the string, the permutation is the last permutation; otherwise, s[i…n-1] is sorted in reverse order, i.e., s[i-1] < s[i] >= s[i+1] >= s[i+2] >= … >= s[n-1].
Find the highest index j to the right of index i such that s[j] is greater than s[i-1] and swap the character at index i-1 with index j.
Reverse substring s[i…n-1] and return true.

The algorithm can be implemented as follows in C++:

#include <iostream>

#include <algorithm>

// Function to rearrange the specified string as lexicographically greater

// permutation. It returns false if the string cannot be rearranged as a

// lexicographically greater permutation; otherwise, it returns true.

bool nextPermutation(std::string &s, int n)

{

// Find the largest index `i` such that `s[i-1]` is less than `s[i]`

int i = n-1;

while (s[i-1] >= s[i])

{

// if `i` is the first index of the string, we are already at the last

// possible permutation (string is sorted in reverse order)

if (--i == 0) {

return false;

}

// If we reach here, substring `s[i…n-1]` is sorted in reverse order.

// Find the highest index `j` to the right of index `i` such that `s[j] > s[i-1]`.

int j = n-1;

while (j > i && s[j] <= s[i-1]) {

j--;

}

// swap character at index `i-1` with index `j`

std::swap(s[i-1], s[j]);

// Reverse substring `s[i…n-1]`and return true

std::reverse (s.begin() + i, s.end());

return true;

}