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

`123`is

`132`.

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 next higher 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 first permutation.

`std::next_permutation` generates the next permutation in just linear time and it can also handle repeated characters, and generates 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 greater permutations of a string int main() { std::string s = "231"; /* Optional: sort the string in natural order before calling std::next_permutation inside a loop to print all permutations, not just the ones that follows specified string lexicographically */ // std::sort(begin(s), end(s)); // find all lexicographically greater permutations using // std::next_permutation while (1) { // print current permutation std::cout << s << " "; // find next permutation in lexicographic order if (!std::next_permutation(begin(s), end(s))) break; } return 0; } |

`Output:`

231 312 321

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

- Find 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 else 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 a highest index j to the right of index i such that s[j] is greater than 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 |
#include <iostream> #include <algorithm> // Function to rearrange the specified string as lexicographically greater // permutation. It returns false if the string cannot be rearranged as // lexicographically greater permutation, else it returns true bool nextPermutation(std::string &s, int n) { // Find largest index i such that s[i-1] is less than s[i] int i = n-1; while (s[i-1] >= s[i]) { // Return false if i is at first index of the string // It means we are already at highest possible permutation if (--i == 0) return false; } // If we reach here, substring s[i..n-1] is sorted in reverse order // Find 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 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 greater permutations of a string int main() { std::string s = "231"; // std::sort(begin(s), end(s)); // find all lexicographically greater permutations using // std::next_permutation while (1) { // print current permutation std::cout << s << " "; // find next permutation in lexicographic order if (!nextPermutation(s, s.length())) break; } return 0; } |

`Output:`

231 312 321

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

**Also See:** std::prev_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