[Leetcode] Next Permutation

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.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

When first do such a problem, we could write some simple example to find the pattern exist in it:

1. For each kind of permutation, there must exist a continuous decreasing sequence, this would be the maximum possible permutation for these numbers.
2. To increase the permutation, we have to choose the lowest possible position, which is the one just in front of this decreasing sequence.
3. In order to make the permutation as small as possible, we need to swap an element from the continuous decreasing sequence with the element mentioned in step 2, we choose the smallest on bigger than it.
4. We need to reorder the continuous decreasing sequence (after swap, it still decreasing) to make it as small as possible

    public void nextPermutation(int[] num) {
        int n = num.length;
        if(n == 0 || n == 1)
            return;
        int p = n - 2;
        while(p >= 0 && num[p] >= num[p + 1])
            p--;
        // All decreasing, there exist no bigger one
        if(p == -1) {
            Arrays.sort(num);
            return;
        }
        int q = n - 1;
        while(q > p && num[q] <= num[p]) 
            q--;
        int temp = num[q];
        num[q] = num[p];
        num[p] = temp;
        
        p = p + 1;
        q = n - 1;
        while(p < q) {
            temp = num[p];
            num[p] = num[q];
            num[q] = temp;
            p++; q--;
        }
     }