Next permutation

Find the next lexicographic arrangement of the array, in place, without listing every permutation.

The idea

Scan from the right for the first index i where the order rises (a[i] < a[i + 1]); everything after i is already the largest possible arrangement of those values. Swap a[i] with the smallest value after it that still beats it, then reverse the falling tail so it becomes the smallest possible arrangement again.

Code

public static void NextPermutation(int[] a) {
    int i = a.Length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) {
        int j = a.Length - 1;
        while (a[j] <= a[i]) j--;
        (a[i], a[j]) = (a[j], a[i]);
    }
    Reverse(a, i + 1, a.Length - 1);
}

static void Reverse(int[] a, int l, int r) {
    while (l < r) { (a[l], a[r]) = (a[r], a[l]); l++; r--; }
}

Tips

• If no such i exists, the whole array is falling: it is the last permutation, and the next one wraps around to the smallest, fully reversed, arrangement.
• The same pivot-then-reverse shape also finds the previous permutation, with every comparison flipped.

In the .NET library

Generating and sorting every permutation to find the next one is O(n!); this in-place scan does it in O(n).