Next Permutation - Python Solution

1. Introduction

The "Next Permutation" problem is a classic in algorithmic thinking, involving rearranging numbers to form the next lexicographically greater permutation. It is often used in computer science to understand concepts related to permutations, combinatorics, and efficient array manipulation.

Problem

Given an array of integers nums, the objective is to rearrange the array to form the next permutation in lexicographical order. If such a permutation is not possible, the array should be rearranged into the lowest possible order (i.e., sorted in ascending order). This rearrangement must be done in place, using only constant extra memory.

2. Solution Steps

1. Start from the end of the array and find the first pair of elements where the preceding element is smaller than the next (i.e., nums[i] < nums[i + 1]). Let's call this index i.

2. If no such index exists, the entire array is in descending order. Reverse the array to get the lowest possible order.

3. If such an index is found, find the smallest element greater than nums[i] after index i. Let's call this element nums[j].

4. Swap nums[i] and nums[j].

5. Reverse the sub-array from i + 1 to the end of the array.

6. The array now represents the next lexicographical permutation.

3. Code Program

def nextPermutation(nums):
    i = j = len(nums) - 1

    while i > 0 and nums[i - 1] >= nums[i]:
        i -= 1
    if i == 0:
        nums.reverse()
        return

    while nums[j] <= nums[i - 1]:
        j -= 1
    nums[i - 1], nums[j] = nums[j], nums[i - 1]

    nums[i:] = reversed(nums[i:])

# Example Usage
nums = [1,2,3]
nextPermutation(nums)
print(nums)  # Output: [1,3,2]

nums = [3,2,1]
nextPermutation(nums)
print(nums)  # Output: [1,2,3]

Output:

[1,3,2]
[1,2,3]

Explanation:

1. Finding the Pivot: Identifies the first element from the end that breaks the descending order.

2. Handling Complete Descending Order: If the entire array is in descending order, reverses it to get the lowest order.

3. Swapping Elements: Swaps the pivot element with the smallest element greater than it found to its right.

4. Reversing Sub-array: Reverses the sub-array after the pivot to ensure the next smallest lexicographical order.

5. In-Place Operation: The rearrangement is done in place, adhering to the constant space requirement.

6. Efficient Algorithm: The solution efficiently finds the next permutation with an O(n) time complexity.

7. Practical Application: Demonstrates an efficient way to handle permutations, which has applications in various fields, including cryptography and combinatorial problems.