Next Permutation

Source: Dev.to

Problem Description

The task is to compute the next permutation of a given array of numbers.
A permutation is a rearrangement of the same elements, and the next permutation is the smallest arrangement that is lexicographically larger than the current one.

Algorithm

1. Find the first decreasing element from the end

Traverse the array from right to left and locate the first index i such that nums[i] nums[i].

3. Swap and reverse the suffix

Swap nums[i] and nums[j]. Then reverse the sub‑array nums[i + 1:] to obtain the smallest possible suffix, completing the next permutation.

Implementation (Python)

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    # Step 1: find the first decreasing element
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: find the element just larger 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 suffix
    nums[i + 1:] = reversed(nums[i + 1:])

Example

nums = [2, 1, 5, 4, 3, 0, 0]
print("Original:", nums)

nextPermutation(nums)
print("Next Permutation:", nums)

Output

Original: [2, 1, 5, 4, 3, 0, 0]
Next Permutation: [2, 3, 0, 0, 1, 4, 5]