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.

  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 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;
}

Tags:

Algorithm