Next Permutation ·

Table of Contents

Introduction
#

The Next Permutation algorithm is used to generate the next lexicographically greater permutation of a given sequence. If no such permutation exists (i.e., the sequence is the largest possible), it rearranges the sequence into its smallest (i.e., sorted in ascending order).

This algorithm is commonly used in problems involving permutation generation, string manipulation, or finding the next configuration in a state space.

Core Idea
#

The goal is to find the next permutation in lexicographic (dictionary) order. The core steps are:

Scan from right to left, and find the first index i such that nums[i] < nums[i + 1]. This is the pivot point.
Find the smallest index j > i such that nums[j] > nums[i].
Swap nums[i] and nums[j].
Reverse the subarray nums[i + 1:] to get the next smallest configuration.

If no such i exists (i.e., the array is in descending order), then the current permutation is the last one. In that case, simply reverse the entire array to get the first permutation.

Template
#

def next_permutation(nums: List[int]) -> None:
    n = len(nums)
    i = n - 2

    # Step 1: Find first decreasing element from the right
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find element just greater than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: Swap
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: Reverse the tail
    nums[i + 1:] = reversed(nums[i + 1:])

Explanation of the key parameters:
#

i: Index of the pivot — the first element from the right that breaks the decreasing trend.
j: The element just greater than nums[i] — to be swapped in.
nums[i + 1:]: The tail of the array — must be reversed to form the smallest possible suffix.