Python - Generate the Next Permutation of an Array

Python – Generate the Next Permutation of an Array

Generating the next permutation of an array is a common problem in coding interviews and helps you understand array manipulation and algorithm design. The goal is to rearrange the array into the lexicographically next greater permutation. If such an arrangement is not possible (i.e., the array is sorted in descending order), then the array should be rearranged as the lowest possible order (sorted in ascending order).

Problem Statement

Given an array arr of numbers, rearrange the numbers to form the next lexicographical permutation. If the array is sorted in descending order, return the ascending order (i.e., the first permutation).

Sample Input and Output

Example 1:

</>

Copy

# Input: arr = [1, 2, 3]
# Output: [1, 3, 2]

Example 2:

</>

Copy

# Input: arr = [3, 2, 1]
# Output: [1, 2, 3]

Solution Approach

To generate the next permutation, follow these steps:

Find the Pivot: Traverse the array from right to left to locate the first element arr[i] that is less than its next element arr[i+1]. This element is the pivot.
Find the Successor: Again traverse from right to left to find the first element arr[j] that is greater than the pivot.
Swap Pivot and Successor: Exchange the values of arr[i] and arr[j].
Reverse the Suffix: Reverse the subarray from arr[i+1] to the end of the array. This step converts the suffix into the lowest possible order.

If no pivot is found (i.e., the array is in descending order), simply reverse the entire array to obtain the smallest permutation.

Python Program

</>

Copy

def next_permutation(arr):
    """
    Generates the next lexicographical permutation for the array.
    If no next permutation exists, rearranges the array into ascending order.
    """
    n = len(arr)
    # Step 1: Find the pivot, the first element from the end which is smaller than its next element.
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find the rightmost element greater than the pivot.
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        # Step 3: Swap the pivot with this element.
        arr[i], arr[j] = arr[j], arr[i]

    # Step 4: Reverse the subarray from i+1 to end to get the next permutation.
    left, right = i + 1, n - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

    return arr

# Example Usage:

# Example 1:
arr1 = [1, 2, 3]
print("Next Permutation:", next_permutation(arr1))
# Expected Output: [1, 3, 2]

# Example 2:
arr2 = [3, 2, 1]
print("Next Permutation:", next_permutation(arr2))
# Expected Output: [1, 2, 3]

Conclusion

The next permutation problem is a great exercise for understanding in-place array manipulation and algorithm design. By identifying the pivot, finding its successor, and reversing the suffix, you can efficiently generate the next lexicographical permutation.

TutorialKart

Python – Generate the Next Permutation of an Array