Next Permutation

Sources: leetcode 31

Rating: medium

Given a list nums, re-arrange the numbers into the lexicographically next greater permutation of numbers. If this is not possible, rearrange it as the lowest possible order (sorted in ascending order). Perform the replacement in-place with constant extra memory.

 def nextPermutation(nums: List[int]) -> None:
    # modify nums in-place into next permutation, do not return anything
        

Solution

First, if there are less than 2 values in nums, no change can be made.

 def nextPermutation(nums):
    if len(nums) < 2:
        return
    # modify nums in-place into next permutation, do not return anything

Next, the trick is to realize what the exactly the “next permutation” is and how to find it. To find the next largest permutation, the arrangement occurs at the right most instance of a digit being less than the one immediately right of it. Use an index i starting from the end of nums and iterating left searching for the first instance.

 def nextPermutation(nums):
    if len(nums) < 2:
        return
    i = len(nums) - 2
    while i >= 0 and nums[i+1] <= nums[i]:
        i -= 1
    # modify nums in-place into next permutation, do not return anything

To begin modifying into the next largest permutation, this found value at nums[i] must be swapped with the next largest value to the right of it. Use an index j starting from the end of the list nums and iterating left searching for the next largest value. Once the two indices i and j are found, transforming to the next largest iteration involves swapping the values at nums[i] and nums[j] and then reversing the order of all the digits from i+1 onward.

 def nextPermutation(nums):
    # define swap
    # define reverse
    if len(nums) < 2:
        return
    i = len(nums) - 2
    while i >= 0 and nums[i+1] <= nums[i]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        swap(nums, i, j)
    reverse(nums, i+1)

Defining reverse is relatively straightforward. Using two indices i and j starting from opposite ends of the list, swap the values while incrementing i and j until they cross one another.

 def nextPermutation(nums):
    # define swap
    def reverse(nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            swap(nums, i, j)
            i += 1
            j -= 1
    if len(nums) < 2:
        return
    i = len(nums) - 2
    while i >= 0 and nums[i+1] <= nums[i]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        swap(nums, i, j)
    reverse(nums, i+1)

Defining the swap function is a trivial switch in the values between nums[i] and nums[j].

Final Code

 def nextPermutation(nums):
    def swap(nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
    def reverse(nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            swap(nums, i, j)
            i += 1
            j -= 1
    if len(nums) < 2:
        return
    i = len(nums) - 2
    while i >= 0 and nums[i+1] <= nums[i]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        swap(nums, i, j)
    reverse(nums, i+1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s