Understanding and Implementing Next Permutation in Rust

Introduction

The “Next Permutation” problem is a fundamental concept in algorithms that involves rearranging numbers in a given array to generate the next lexicographical permutation. If such a permutation is not possible (the array is in descending order), the smallest permutation is returned.

In this article, we will delve into the algorithm’s details and its implementation in Rust. We’ll also discuss each step with examples for a comprehensive understanding.

Problem Statement

Given an array of integers nums, rearrange the array into its next lexicographical permutation. If no such arrangement is possible, rearrange it as the lowest possible order (i.e., sorted in ascending order).

Algorithm Overview

1. Find the first decreasing element: Traverse the array from the end to find the first element that breaks the descending order.
2. Find the next larger element: Locate the smallest element to the right of the found element that is greater than it.
3. Swap the elements: Swap these two elements.
4. Reverse the suffix: Reverse the subarray starting from the index after the swapped element to the end to ensure it’s in the smallest order.

Implementation in Rust

Here is the Rust implementation of the algorithm:

impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        let n = nums.len();
        if n <= 1 {
            return;
        }
        // Step 1: Find the first decreasing element from the right
        let mut i = (n - 2) as isize;
        while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
            i -= 1;
        }
        // Step 2: If a decreasing element is found, find the next larger element
        if i >= 0 {
            let mut j = n - 1;
            while nums[j] <= nums[i as usize] {
                j -= 1;
            }
            // Swap the two elements
            nums.swap(i as usize, j);
        }
        // Step 3: Reverse the suffix starting from index i + 1
        nums[(i as usize + 1)..].reverse();
    }
}

Step-by-Step Explanation

Step 1: Find the First Decreasing Element

Start from the right and find the first element that is smaller than the element next to it. This marks the end of the current lexicographical order.

Example: For nums = [1, 3, 2], the first decreasing element is 1 (index 0).

Step 2: Find the Next Larger Element

Find the smallest element to the right of the decreasing element that is greater than it.

Example: For nums = [1, 3, 2], the next larger element to 1 is 2 (index 2).

Step 3: Swap the Two Elements

Swap the two elements found in steps 1 and 2.

Example: After swapping 1 and 2 in nums = [1, 3, 2], we get nums = [2, 3, 1].

Step 4: Reverse the Suffix

Reverse the portion of the array after the index of the first element swapped to get the smallest order.

Example: After reversing the suffix in nums = [2, 3, 1], we get nums = [2, 1, 3].

Example Walkthrough

Input:

let mut nums = vec![1, 2, 3];
Solution::next_permutation(&mut nums);
println!("{:?}", nums);

Output:

[1, 3, 2]

Explanation:

• Current permutation: [1, 2, 3].
• Step 1: First decreasing element is 2 at index 1.
• Step 2: Next larger element is 3 at index 2.
• Step 3: Swap 2 and 3 to get [1, 3, 2].
• Step 4: Reverse suffix (none in this case) to get [1, 3, 2].

Edge Cases

Descending Order:

• Input: [3, 2, 1]
• Output: [1, 2, 3] (reset to smallest permutation)

Single Element:

• Input: [1]
• Output: [1] (no change)

All Elements Equal:

• Input: [2, 2, 2]
• Output: [2, 2, 2] (no change)

Complexity Analysis

Time Complexity:

• Traversing the array takes O(n).
• Reversing the suffix takes O(n).
• Overall complexity: O(n).

Space Complexity:

• In-place operations mean the space complexity is O(1).

Conclusion

The “Next Permutation” algorithm is an elegant solution to finding the next lexicographical order. This Rust implementation mirrors the logic of its C++ counterpart while adhering to Rust’s idiomatic practices, ensuring safety and performance.

By understanding each step and considering edge cases, you can confidently handle this problem in both interviews and real-world applications. Experiment with the implementation to deepen your understanding!