LC 0031 [M] Next Permutation - ALawliet/algorithms GitHub Wiki

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

rightmost = while not, ptr--
non-increasing = descending

1. i = longest non-increasing (descending) suffix from right
2. if i = 0, everything is already descending, reverse the whole thing so it's ascending and return early
3. p = the furthest ascending position from left = 1 behind the suffix (suffix - 1)
4. j = rightmost successor (ascending) to pivot in the suffix
5. Swap rightmost successor with pivot (j <-> p)
6. Reverse the suffix (after p+1)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        r = n - 1 # start from the right end

        # 1. Find start of longest non-increasing (decreasing) suffix from right \
        while r > 0 and not nums[r-1] < nums[r]: # nums[r-1] >= nums[r]
            r -= 1

        # ended up at 0, all nums are already in decreasing order, just reverse to increasing and finish early /
        if r == 0:
            nums.reverse()
            return

        # 2. Identify pivot = the furthest increasing position from left or (easier) 1 behind the suffix p\
        p = r - 1

        r = n - 1
        # 3. Find rightmost successor (increasing) to pivot in the suffix p...o
        while not nums[r] > nums[p]: # while nums[r] <= nums[p]
            r -= 1

        # 4. Swap rightmost successor with pivot
        nums[r], nums[p], = nums[p], nums[r] # swap r, p

        # 5. Reverse the suffix (after the pivot to the end)
        l = p + 1
        r = n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l] # swap l, r
            l += 1 ; r -= 1