Next lexicographical permutation algorithm

Next lexicographical permutation algorithm

Suppose we have a finite sequence of numbers (e.g. (0, 3, 3, 5, 8)) and want to generate all its permutations. What's the best way to do this?

As a matter of fact, the best approach to generating all the permutations is to start at the lowest permutation and repeatedly compute the next permutation in place. The simple and fast algorithm is what will be described on this page. We will use concrete examples to illustrate the reasoning behind each step of the algorithm.

Condensed mathematical description:

1. Find largest index i such that array[i − 1] < array[i].
2. Find largest index j such that j ≥ i and array[j] > array[i − 1].
3. Swap array[j] and array[i − 1].
4. Reverse the suffix starting at array[i].

Now if you truly understand the algorithm, here’s an extension exercise for you: Design the algorithm for stepping backward to the previous lexicographical permutation.

boolean nextPermutation(int[] array) {
    // Find longest non-increasing suffix
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    // Now i is the head index of the suffix
    
    // Are we at the last permutation already?
    if (i <= 0)
        return false;
    
    // Let array[i - 1] be the pivot
    // Find rightmost element that exceeds the pivot
    int j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    // Now the value array[j] will become the new pivot
    // Assertion: j >= i
    
    // Swap the pivot with j
    int temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
    
    // Reverse the suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    
    // Successfully computed the next permutation
    return true;
}

This code can be mechanically translated to a programming language of your choice, with minimal understanding of the algorithm. (Note that in Java, arrays are indexed from 0.)

https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/nextperm.java

Read full article from Next lexicographical permutation algorithm