In this post, we will discuss about std::prev_permutation which can be used to find the lexicographically smaller permutations of a string.

`213`is

`132`.

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 previous permutation exists, else 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 also handle repeated characters to generate the distinct permutations. Below C++ program demonstrates its usage:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <algorithm> // Program to find lexicographically smaller permutations of a string 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 follows specified string lexicographically */ // std::sort(rbegin(s), rend(s)); // find all lexicographically smaller permutations using // std::prev_permutation while (1) { // print current permutation std::cout << s << " "; // find previous permutation in lexicographic order if (!std::prev_permutation(begin(s), end(s))) break; } return 0; } |

`Output:`

231 213 132 123

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

- Find 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 else 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 a highest index j such that j >= i and s[j] < s[i-1] and swap characters at index i-1 with index j.

- Reverse the substring s[i..n-1] and return true

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <algorithm> // Function to rearrange the specified string as lexicographically smaller // permutation. It returns false if the string cannot be rearranged as // lexicographically smaller permutation, else it returns true bool prevPermutation(std::string &s, int n) { // Find 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 first index of the string // This means we're already at lowest possible permutation if (--i == 0) return false; } // s[i..n-1] is now sorted in natural order // Find 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 characters at index i-1 with index j std::swap(s[i-1], s[j]); // Reverse the substring s[i..n-1] and return true std::reverse (s.begin() + i, s.end()); return true; } // Program to find lexicographically smaller permutations of a string int main() { std::string s = "231"; // std::sort(rbegin(s), rend(s)); // find all lexicographically smaller permutations using // std::prev_permutation while (1) { // print current permutation std::cout << s << " "; // find previous permutation in lexicographic order if (!prevPermutation(s, s.length())) break; } return 0; } |

`Output:`

231 213 132 123

Since there are `n!` permutations and each permutations takes linear time, the time complexity of above solution is `O(n.n!)`. Here n is the length of the given string. The worst case happens when the string contains all distinct elements and the best case happens when the string contains all repeated characters.

**Also See:** std::next_permutation

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply