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

This post discusses std::prev_permutation, which can be used to find the lexicographically smaller 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 previous permutation in lexicographic order for string 213 is 132.

The STL provides std::prev_permutation, which returns the previous permutation in lexicographic order by in-place rearranging the specified object as a lexicographically smaller permutation. The function returns true if the previous 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 last permutation.

std::prev_permutation generates the previous permutation in mere linear time and handles repeated characters to generate the distinct permutations. Following is the C++ program which demonstrates its usage:

#include <iostream>

#include <algorithm>

int main()

{

std::string s = "231";

/* Optional: sort the string in reverse order before calling

std::prev_permutation to print all permutations, not just the ones

that follow specified string lexicographically */

// std::sort(rbegin(s), rend(s));

// find all lexicographically smaller permutations using

// std::prev_permutation

while (1)

{

// print the current permutation

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

// find the previous permutation in lexicographic order

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

break;

}

return 0;

}

Download Run Code

Output:

231 213 132 123

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

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

The implementation can be seen below in C++:

#include <iostream>

#include <algorithm>

// Function to rearrange the specified string as lexicographically smaller

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

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

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

{

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

int i = n-1;

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

{

// Return false if `i` is at the first index of the string.

// This means we are already at the lowest possible permutation

if (--i == 0) {

return false;

}

/* Substring `s[i…n-1]` is now sorted in a natural order */

// Find the highest index `j` such that `j >= i` and `s[j] < s[i-1]`

int j = i;

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

j++;

}

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;

}