Next Permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Example:

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Solution:

Assume we have [1,2,6,7,3,2,1],

1. we need to find the first increasing trend (which is 6 and 7) from the back, we choose the index 2 (value:6)
2. find the first greater number from back when compared with 6. From the list we know the number is 7
3. swap them, we will have [1,2,7,6,3,2,1]
4. reverse the order between index 3 and the end, [1,2,7,6,3,2,1] => [1,2,7,1,2,3,6]

When we have [4,3,2,1], we are not able to find any increasing trend, then we simply reverse this entire array to [1,2,3,4].

Code:

public class Solution {

    public int[] nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        //find the last increase index
        int index = -1;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                index = i - 1;
                break;
            }
        }
        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return nums;
        }

        //find the first bigger num from back
        int biggerIndex = index + 1;
        for (int i = nums.length - 1; i > index; i--) {
            if (nums[i] > nums[index]) {
                biggerIndex = i;
                break;
            }
        }
        swap(nums, index, biggerIndex);
        reverse(nums, index + 1, nums.length - 1);
        return nums;
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    private void reverse(int[] nums,  int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}