Next Permutation

Question

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

Tags

• Array

Thought

The approach is very straightforward:

1. Loop from the rightmost in the input array until finding two neighboring integers and the previous integer is smaller than the next integer.
2. Divide the original array at the position we stop in the loop.
3. Find the integer which is only larger than the integer at the rightmost of the left part of the original array. Then swap these two integers.
4. Sort the right part of the original array and recombine them together.

Code

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums) != 0:
            index = len(nums) - 1
            subList = []
            while index > 0:
                subList.append(nums[index])
                if nums[index] > nums[index - 1]:
                    break
                index -= 1
            if index == 0:
                nums.reverse()
            else:
                subList.sort()
                for i in xrange(len(subList)):
                    if subList[i] > nums[index - 1]:
                        nums[index - 1], subList[i] = subList[i], nums[index - 1]
                        break
                nums[index:] = subList[:]