Algorithm to find next greater permutation of a given string
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 thats[i] < s[i+1]
. If no such index exists, the permutation is the last permutation.- Find the highest index
j > i
such thats[j] > s[i]
. Such aj
must exist, sincei+1
is such an index.- Swap
s[i]
withs[j]
.- Reverse the order of all of the elements after index
i
till the last element.
A great solution that works is described here: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. And the solution that, if next permutation exists, returns it, otherwise returns false
:
function nextPermutation(array) {
var i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i <= 0) {
return false;
}
var j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}