31. Next Permutation

Description of Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Solution

Tags: Permutation and Combination

Explanation

The explanation just follow the offical answer and Back To Back SWE's video:

The solution has 3 steps:

  1. Find the pivot and the right sublist.
  2. Swapping pivot and the rightmost number from right sublist that just greater than pivot.
  3. Reversing the right sublist.

Explanation part 0:

To find next permutation, we have to find the next greater number composed by the list of numbers.

Notice that the list of non-ascending numbers does not have next permutation since it composes the largest number. For example, [9 7 5 5 2 1] does not have next permutation.


Explanation part 1:

To generate next permutation, we must first find the sublist from the right that is in non-ascending order since it is not possible to re-arrange them to get the greater number.

For instance, in [9 7 1 5 5 2], it's not possible to get greater permutation by re-arrrangement of [5 5 2].

We call the left neighbour of the sublist a pivot. In the above example, 1 is the pivot.


Explanation part 2:

The next step is to swap the pivot and the rightmost minimum number from the sublist that just greater than the pivot.

[1]: Since the sublist will be reversed later. We choose the right most one to make sure the the reversed number is the minimum one.


Explanation part 3:

After swapping, the sublist still compose the greatest number as swapping does not change the order[2]. Thus, it is not the next greater number. To get the number we must reverse the right sublist.

[2]: (Optional) Prove that the swapping does not change the order of the sublist:

Consider the following list which \(a_i\) is the pivot, \([a_{i}, ..., a_{n-1} ]\) is the right sublist and \(a_j\) is the chosen number to be swapped. \[ [... a_i \lt a_{i+1} \ge ... \ge a_{j-1} \ge a_{j} \ge a_{j+1} \ge ... \ge a_{n-1}] \]

There are 4 facts have to be reminded:

  1. \( a_i \lt a_j \)
  2. \( a_j \le a_{j-1} \)
  3. \( a_{j+1} \le a_{j} \)
  4. \( \forall k \in \lbrace i+1, ..., n-1 \rbrace ( a_i \lt a_k \rightarrow a_j \le a_k ) \)
    • since \(a_j\) is the minimum number amongst the numbers that greater than \(a_i\)

From fact (1) and fact (2), we get \( a_{j-1} \ge a_{i} \).

Assume \( a_{i} \lt a_{j+1} \), we get \( a_{j} \le a_{j+1} \) from fact (4) which contradicts the fact (3). Thus, \( a_{i} \ge a_{j+1} \).

We conclude that the swapping does not change the order:

\[ [... a_j \lt a_{i+1} \ge ... \ge a_{j-1} \ge a_{i} \ge a_{j+1} \ge ... \ge a_{n-1}] \]

Q.E.D.

Code (Rust)

impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) {
        if let Some(i) = Self::find_pivot(nums) {
            let j = Self::find_target(nums, i);
            nums.swap(i,j);
            &mut nums[i+1..].reverse();
        } else {
            nums.reverse();
        }
    }

    fn find_pivot(nums : &[i32]) -> Option<usize> {
        if nums.len() < 2 {
            return None;
        }

        let (mut i, mut j) = (nums.len() - 2, nums.len() - 1);
        while /*i >= 0  &&*/ j >= 1 {
            if nums[i] < nums[j] {
                return Some(i);
            }
            i = i.checked_sub(1).unwrap_or(0);
            j = j.checked_sub(1).unwrap_or(0);
        }

        return None;
    }

    // find the right most index 
    // such that its elements is the smallest number
    // which greater than the pivot value
    fn find_target(nums : &[i32], pivot : usize) -> usize {
        let pivot_value = nums[pivot];
        let mut target_index = pivot+1;
        let mut target_value = nums[target_index];
        for j in pivot+2..nums.len() {
            let v = nums[j];
            if v > pivot_value && v <= target_value {
                target_value = v;
                target_index = j;
            }
        }
        return target_index;
    }
}

Complexity

Time Complexity

  • \(T(n) = O(n)\)

Auxiliary Space

  • \(S(n) = O(1)\)

Appendix A1 - Implementation of Permutation Iterator

pub struct PermutationIterator<T : Ord + Clone>(Option<Vec<T>>);

impl<T : Ord + Clone> PermutationIterator<T> {

    pub fn new(mut elements : Vec<T>) -> Self {
        elements.sort();
        PermutationIterator(Some(elements))
    }

    fn next_permutation(&mut self) -> Option<Vec<T>> {
        let res = self.0.clone();

        self.0 = self.0.take().and_then(|mut v|{
            let i = Self::find_pivot(&v)?;
            let j = Self::find_target(&mut v,  i);
            v.swap(i,j);
            let _ = &mut v[i+1..].reverse();
            Some(v)
        });

        return res;
    }

    fn find_pivot(elements : &[T]) -> Option<usize> {
        if elements.len() < 2 {
            return None;
        }

        let (mut i, mut j) = (elements.len() - 2, elements.len() - 1);
        while /* i >= 0  && */ j >= 1 {
            if elements[i] < elements[j] {
                return Some(i);
            }
            i = i.checked_sub(1).unwrap_or(0);
            j = j.checked_sub(1).unwrap_or(0);

        }

        return None;
    }

    // find the right most index 
    //  such that its elements is the smallest number 
    //  which greater than the pivot value
    fn find_target(elements : &mut [T], pivot : usize) -> usize {
        let pivot_value = &elements[pivot];
        let mut target_index = pivot+1;
        let mut target_value = &elements[target_index];
        for j in pivot+2..elements.len() {
            let v = &elements[j];
            if v > pivot_value && v <= target_value {
                target_value = v;
                target_index = j;
            }
        }
        return target_index;
    }
}

impl<T : Ord + Clone> Iterator for PermutationIterator<T> {
    type Item = Vec<T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_permutation()
    }
}