Algorithm to find next greater permutation of a given string.

Question

Hello all,

I want an efficient algorithm to find the next greater permutation of the given string.

Answer 1

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.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse all the order of all of the elements after index i

Answer 2

Homework? Anyway, can look at the C++ function std::next_permutation, or this:

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html