[Leetcode] Next Permutation

Problem

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 (i.e., sorted in ascending order). For example, 

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

The replacement must be in-place, do not allocate extra memory.

Algorithm

See some examples first. 

1,2,3  ->  1,3,2  ->  2,1,3  ->  2,3,1  ->  3,1,2  ->  3,2,1  ->  1,2,3

The next permeation can be found in following four steps: 

1. Scan from right to left, find the pivot such that A[p] < A[p+1].
2. Find the smallest number A[q] which is larger than A[p] in range A[p+1 to end].
3. Swap A[p] and A[q]. 
4. Sort A[p+1 to end] in ascending order. 

For example, for input A = [2,4,3,1]. 

                                         [2,4,3,1] => [2,4,3,1] => [2,4,3,1] => [3,4,2,1] => [3,1,2,4]

                                                              p                  p     q   

For a subarray like [4,3,1], we cannot increase it without changing the first digit, i.e. the "2". In order to find the next permutation, the "2" must be replaced by the "smallest number in [4,3,1] larger than 2". After swapping "2" and "3", the array is still not the next permutation.   After sorting the subarray A[p+1 to end], we obtain the result. 

When the whole array is in the descending order, we simply sort the array in ascending order. 

To change an array from descending order to ascending order, simply swap each pair of numbers, as shown in the code. 

In the code, we do the step 4 first. 

Note, 

Code