31. Next Permutation - cocoder39/coco39_LC GitHub Wiki

31. Next Permutation

notes 2024:

attention to boundary conditions caused by duplicated numbers eg 1, 5, 1 -> 5, 1, 1 -> 1, 1, 5

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        n = len(nums)
        if n <= 1:
            return

        # right to left, index of first decending value
        decending_idx = n - 2 
        while decending_idx >= 0 and nums[decending_idx] >= nums[decending_idx+1]:
            decending_idx -= 1
        
        # no decending value, so right to left ascending, so left to right descending
        if decending_idx == -1: # 3 2 1
            nums.reverse()
            return
        
        # right to left, smallest value that is greater than nums[decending_idx]
        # such value is guaranteed available, otherwise decending_idx == -1
        swap_idx = n - 1
        while swap_idx > decending_idx and nums[swap_idx] <= nums[decending_idx]:
            swap_idx -= 1

        # swap to get next bigger value
        nums[swap_idx], nums[decending_idx] = nums[decending_idx], nums[swap_idx]

        # sort the rest
        left, right = decending_idx + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Notes 2021:

Option 1: O(N^2)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n-2, -1, -1):
            swap = -1
            for j in range(i+1, n):
                if nums[j] > nums[i]:
                    if swap == -1 or nums[j] < nums[swap]:
                        swap = j
            if swap != -1:
                nums[i], nums[swap] = nums[swap], nums[i]
                nums[i+1:] = sorted(nums[i+1:])
                return nums
        
        nums.sort()

Observations after implementing option 1:

  • sequence nums[i+1:] is in descending order
  • once i and swap get swapped, sequence nums[i+1:] is still in descending order

The 2 Observations are then used to derive option 2

Option 2: O(N)

Given 1 5 8 _4_ 7 6 5 3 1
step 1: 从右向左找到descending number (4 in this case)
step 2: 从右向左找到第一个比4大的数（5 in this case）
step 3: swap 4 and 5 -> 1 5 8 _5_ 7 6 _4_ 3 1
step 4: reverse 5（新位置）右边的数 -> 1 5 8 5 _1 3 4 6 7_

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        startIdx = n-2
        while startIdx >= 0:
            if nums[startIdx] < nums[startIdx+1]:
                break
            startIdx -= 1
        
        if startIdx == -1:
            nums.sort()
            return
        
        for i in range(n-1, startIdx, -1):
            if nums[i] > nums[startIdx]:
                nums[i], nums[startIdx] = nums[startIdx], nums[i]
                break
        
        left, right = startIdx+1, n-1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

===========================================================================

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

the begin of permutation is an ascending array, the end is a descending array

  • from the end to the begin, finding out the first element arr[i] that violates the descending order of arr[i .. n-1]. 6 in example. since arr[i .. n-1] is in descending order, it is the end permetation of the subarray [8 7 4 3 2]. next permutation would replace 6 with a greater element and pertumuate the right side from begining (ascending order)
  • swap it with element within arr[i+1, n-1] that is closest to it among elements greater than it. 7 in example
  • sort the sequence behind i (reverse is enough)
i  
6 8 7 4 3 2

7 8 6 4 3 2

7 2 3 4 6 8

time is O(n)

void nextPermutation(vector<int>& nums) {
        int idx = nums.size() - 2;
        for (; idx >= -1; idx--) {
            if (idx == -1 || nums[idx] < nums[idx + 1]) {
                break;
            }
        }
        
        if (idx > -1) { 
            for (int i = nums.size() - 1; i > idx; i--) {
                if (nums[i] > nums[idx]) {
                    swap(nums[i], nums[idx]);
                    break;
                }
            }
        } 
        
        int start = idx + 1, end = nums.size() - 1;
        while (start < end) {
            swap(nums[start++], nums[end--]);
        }
    }
⚠️ **GitHub.com Fallback** ⚠️