[LeetCode] Next Permutation

leetcode

This is a tricky problem. Instead of thinking it as permutations, I suggest look at it as numbers. Therefore the next permutation is simply the next smallest number possible consists of those digits.

After observation, we can see some pattern in the examples:

  • If the last n digits are not in descending order, that mean you simply need to re-order them to make the next possible smallest number
  • However, if the last n digits are already in descending order, you have to change the last n+1 digit to make this happen because the last n digits is already the biggest number
  • If all the digits are in descending order, the next permutation the everything in ascending order

From these rules, we can construct a formula:

And thus the code below: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param nums: A list of integers
    @return: A list of integers
    """
    def nextPermutation(self, nums):
        # write your code here
        if len(nums) <= 1:
            return nums
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                break
        n = nums[i]
        a = nums[:i]
        b = nums[i:]
        b = sorted(b)
        m = None
        for i in range(len(b)):
            if b[i] > n:
                m = b[i]
                del b[i]
                break
        if m is None: return a + b
        return a + [m] + b