Algorithm to find next greater permutation of a given string
algorithm
Solution
Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.
Quoting:
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the highest index `i` such that `s[i] < s[i+1]`. If no such index exists, the permutation is the last permutation.
- Find the highest index `j > i` such that `s[j] > s[i]`. Such a `j` must exist, since `i+1` is such an index.
- Swap `s[i]` with `s[j]`.
- Reverse the order of all of the elements after index `i` till the last element.
Problem
I want an efficient algorithm to find the next greater permutation of the given string.