題目出處

31. Next Permutation

難度

medium

個人範例程式碼

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

        last = len(nums)-1
        while(last > 0):
            if nums[last-1] < nums[last]: # ...last-2, last-1, last # 34 -> 43  
                self.change_inplace(nums, last-1) 
                return 
            last -= 1

        else: # all descend
            # nums.reverse() 
            self.inplace_reverse(nums, 0, len(nums)-1)
            return 

    def change_inplace(self, nums, idx):
        change_idx = self.find_next_same_or_bigger(nums, idx)
        nums[change_idx], nums[idx] = nums[idx], nums[change_idx] # inplace
        self.inplace_reverse(nums, idx+1, len(nums)-1) # inplace reverse after idx, nums[:idx]
        return 

    def find_next_same_or_bigger(self, nums, idx):
        last = len(nums)-1
        target = nums[idx]
        while nums[last] <= target:
            last -= 1
        else:
            return last

    def inplace_reverse(self, nums, start, end):
        while(start < end):
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
            print(nums)
        return 

算法說明

排列問題的進階版，求「下一個排列」，
直接的做法可以簡單歸納為，

1. 從結尾處開始找「第一個」往下的地方
2. 如果找到了，交換「往下的那個」與「之前往上的過程中 <= 此數的數字 (注意等於)」，交換後把整個數列顛倒
3. 如果找不到，下一個數字就是全部順序直接顛倒 (也就是第一個數字)

圖片說明

我們找第一個往下的地方，上面我們有標示箭頭，
將「在下的位置」與「之前上升時，>= 下降數的第一個數字」交換

注意這邊可以多留意 [1,1,5] -> [1.5.1] 這個 case，可以解釋為何要處理 「>=」

交換後，我們會發現之前的上升順序還是會保持上升，我們直接顛倒方向，使後綴的部分呈現下降順序。

以文字說明 – 1 (邊看圖想會比較懂在做什麼)：

1. 1243 我們抓到下降的 4->2，
2. 2 與第一個 3 (>=2)交換，此時為 1342，
3. 把交換處之後的倒序，變成 1324，就是下一個數字

以文字說明 – 2 (邊看圖想會比較懂在做什麼)：

1. 1342 我們抓到下降的 4->3，
2. 3 與第一個 4 (>= 3)交換，此時為 1432，
3. 把交換處之後的倒序，變成 1423，就是下一個數字

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

• 這邊也可以參考 leetcode 上很讚的圖片說明版：

Easy python solution based on lexicographical permutation algorithm

input handling

如果沒有 nums，回傳 nums

Boundary conditions

做完上述的交換後，return 結果

Reference

• Easy python solution based on lexicographical permutation algorithm
• 下一个排列 · Next Permutation
• Python solution with comments.