LeetCode - Next Permutation | Darren's Blog

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory

In order to find the next permutation of s , we need to (1) identify such index i as large as possible, (2) swap the digit at index i with the smallest larger value behind it, and (3) rearrange the digits after it in non-descending order. Because of (2), (1) can be achieved by identifying the first increasing adjacent pair in the reverse order, where i is the the index of the first digit. Otherwise, there would be no value greater the digit at index i . And after (2), the digits after index i must be in non-increasing order (prove this yourself). What is left is to reverse them.

public void nextPermutation(int[] num) {

        int n = num.length;

        int a;

        // Find the first increasing adjacent pair in the reverse order;

        // a is the index of the first number of the pair

        for (a = n-2; a >= 0; a--)

            if (num[a] < num[a+1])

                break;

        // The array is in non-increasing order;

        // already the maximum, goes to the smallest

        if (a < 0) {

            reverse(num, 0);

            return;

        }

        // min is the index of the smallest number behind num[a]

        // that are larger than num[a]

        int min = a + 1;

        for (int i = a+2; i < n; i++) {

            if (num[i] <= num[a])

                break;

            if (num[i] <= num[min])

                min = i;

        }

        // Swap num[a] and num[min]

        int temp = num[a];

        num[a] = num[min];

        num[min] = temp;

        // Reverse num[a+1..]

        reverse(num, a+1);

    }

 

Read full article from LeetCode - Next Permutation | Darren's Blog