60. Permutation Sequence

Description of the Problem

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Solution

Tags: Permutation and Combination

*The following explanation assume 0-based indexing which is different from the problem*

Explanation

\[ n! = \underbrace{n}_{\text{#possible choices for 1st element}} \cdot \underbrace{(n-1)!} _ {\text{#permutation start with specific element}} \]

Example: n = 4, k = 13

0: 1234     6: 2134    12: 3124    18: 4123
1: 1243     7: 2143    13: 3142    19: 4132
2: 1324     8: 2314    14: 3214    20: 4213
3: 1342     9: 2341    15: 3241    21: 4231
4: 1423    10: 2413    16: 3412    22: 4312
5: 1432    11: 2431    17: 3421    23: 4321

Solution: 3142

Because: \[ \underbrace{2} _{3!\text{: choose arr[2] from[1,2,3,4]}} \
\underbrace{0} _{2!\text{: choose arr[0] from[1,2,4]}} \
\underbrace{1} _{1!\text{: choose arr[1] from[2,4]}} \
\underbrace{0} _{0!\text{: choose arr[0] from[2]}} \]

As we see, there are \( (n−1)! \) permutations start with some particular element.

Thus, the element we want to find is in position \(\left \lfloor \frac{index}{(n-1)!} \right \rfloor\) in sorted array.

For the permutation of remaining (n-1) elements, the index for this sub-permutation will be \( \text{index} \ mod (n−1)! \) because \(divisor \cdot quotient + remainder = original \ number\).

Therefore, we can use the same method for (\(n-1)\) elements with \(\text{index′}=\text{index} \ mod (n−1)! \)

Code (Rust)

impl Solution {
    fn fact(n: usize) -> usize{
        if n <= 1 {
            1
        }else{
            (2..=n).product()
        }
    }

    fn dfs( choice : Vec<usize>, index: usize) -> String{

        if choice.is_empty() {
            return String::from("");
        }

        if index == 0 {
            return choice.into_iter().map(|x| x.to_string()).collect::<String>();
        }

        let mut choice = choice;
        let group_size = Solution::fact(choice.len() - 1);
        let group_index = index / group_size;
        let subgroup_index = index % group_size;

        let left = choice.remove(group_index).to_string();
        let right = Solution::dfs(choice,subgroup_index);

        return [left, right].join("");

    }

    pub fn get_permutation(n: i32, k: i32) -> String{
        let n = n as usize;
        let k = k as usize;
        let mut choice = (1..=n).collect::<Vec<usize>>();
        return Solution::dfs(choice, k - 1);
    }
}

Complexity

Time Complexity

• \(T(n) = \mathcal{\Theta(n)}\)

Auxiliary Space

• \(S(n) = \mathcal{\Theta(n)}\)