Next Permutation

Problem: Next Permutation

We can get how we get to next permutation from observation. We need to find the first descending number from right to left, then we find the first number larger than it from right to left. Then we change one number to another and reverse the following part.

For example, For permutation [1,2,4,3], we first find out that we need to change number 2, then we find out that 3 is a choice to change 2. After changing, we get [1,3,4,2], which means we need to reverse the part following number 3 to achieve the right answer.

Code in Python:

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        x = None
        for i in xrange(len(nums)-2,-1,-1):
            if nums[i] < nums[i+1]:
                x = i
                break
        if x == None:
            nums[:] = nums[::-1]
            return
        y = None
        for i in xrange(len(nums)-1,x,-1):
            if nums[i] > nums[x]:
                y = i
                break
        nums[x], nums[y] = nums[y], nums[x]
        nums[x+1:] = nums[:x:-1]

Code in Java:

public class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n == 1 || n == 0) return;

        for (int i = n-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                for (int j = n-1; j >= i; j--) {
                    if (nums[j] > nums[i]) {
                        int tmp1 = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp1;
                        for (int k = i+1; k < i+1+(n-i)/2; k++) {
                            int tmp2 = nums[k];
                            nums[k] = nums[n-(k-i)];
                            nums[n-(k-i)] = tmp2;
                        }
                        return;
                    }
                }
            }
        }

        for (int i = 0; i < n/2; i++) {
            int tmp3 = nums[i];
            nums[i] = nums[n-i-1];
            nums[n-i-1] = tmp3;
        }

        return;
    }
}