LC31 next permutation

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).

We can think lexicographical order like regular number. The bigger the number, the later in the order is a number. For example, 321 is bigger than any permutation of 3,2,1 so it is the biggest number in lexicographical order.

What is in the biggest number.

The biggest number with 3 number is 321. It has the characteristics that the largest number is placed at the very beginning. The second largest number is placed in the second most significant place.

So the kth biggest number is placed on the kth place in the number for the biggest number.

In other word, when going through the number reversely, it will be monotonically increasing.

What kind of number can be increased

A number can be increased in lexicographical order when the kth place contain a number that’s smaller than the kth large number. EG: 123 can be increased because the 1 th place contain 1, which is smaller than the 1st largest number.

How to find the next permutation?

Find the smallest number larger than the number that breaks the monotone increase and swap it with the number that breaks the monotone increase

For next permutation, we first need to determined if it is the biggest number by going from back to front. If we see a decrease at k, we know that there are a number in nums[k, end] that is bigger than nums[k].

To find the next permutation, we want to new number to be bigger and to be the **Smallest number bigger ** than the current number.

Even though we know nums[k] < nums[k + 1], we need to sub nums[k] with the smallest number that’s larger than nums[k], so we scan nums[k + 1 : end] to find it and then swap.

Flip the list from k + 1 to end (k is where the number that breaks monotone is at)

After the swap, we also need to make nums[k + 1 : end] is the smallest permutation. Assume we swapped nums[k] with nums[j] where k < j < end.

To find the smallest permutation from nums[k + 1 : end], we need to make sure the numbers are monotone increasing from k + 1 till end. Before the swap happened, nums[k + 1 : end] was monotone decreasing from k + 1 to end. So we can just flip nums[k + 1 : end] to achieve smallest permutation among nums[k + 1 : end]. But after the swap, with nums[k] at j, is it still the case?

Basically, we want to maintain

  1. nums[j + 1] < nums[k]
  2. nums[k] < nums[j – 1]

after we swap nums[k] into nums[j]

nums[k] < nums[j – 1]

We know nums[k] < nums[j], and smaller sign commutes, so nums[k] < nums[j] < nums[j – 1] and no.2 holds.

nums[k] > nums[j + 1]

we knows nums[j] > nums[j + 1] because nums[k…j…end] is monotone decreasing. But nums[k] < nums[j], so we can’t confirm nums[k] > nums[j + 1] directly.

Use prove by contradiction: assume nums[k] < nums[j + 1]. Then nums[j + 1] > nums[k]. We recall that nums[j + 1] < nums[j] so nums[j + 1] is the smallest number larger than nums[k], not nums[j]. This is a contradiction so nums[k] > nums[j + 1].

So after the swapping, the sequence nums[k + 1 : end] is still monotone decreasing from k + 1 till end so it is the largest permutation for numbers in nums[k + 1 : end]. We only need to flip nums[k + 1: end] to achieve the smallest permutation

code

    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        for i in range(len(nums) - 1, 0, -1):
            right_num = nums[i]
            left_num = nums[i - 1]
            if right_num > left_num:  #break monotone increase, 
                #need to find the smallest num larger than left_num from nums[i:]
                smallest_pos = i

                for j in range(i, len(nums)):
                    if nums[j] <= nums[smallest_pos] and nums[j] > left_num:
                        smallest_pos = j
                smallest = nums[smallest_pos]
                nums[smallest_pos] = nums[i - 1]
                nums[i - 1] = smallest

                for j in range((len(nums) - i) // 2):
                    temp = nums[i + j]
                    nums[i + j] = nums[len(nums) - j - 1]
                    nums[len(nums) - j - 1] = temp

                return

        for i in range(len(nums) // 2):
            temp = nums[len(nums) - 1 - i] 
            nums[len(nums) - 1 - i] = nums[i]
            nums[i] = temp
        return

subtle bug I had

<= instead of <

At

if nums[j] <= nums[smallest_pos] and nums[j] > left_num:

I first didn’t use <= but <. So the code will update the smallest only when it sees a number smaller than smallest.
This will break for input like [2,3,1,3,3]
We will settle with smallest_pos at 3 instead of 4.After the swap, we have [2,3,3,1,3], which breaks the assumption that from nums[k + 1 : end], we have the max permutation.

To maintain this assumption, we need to let the smallest_pos goes to as far back as possible toward the least significant digit. So we use <=.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax