# LeetCode Algorithm 0060 - Permutation Sequence (Medium)

2020-11-13 00:31:02

# LeetCode Algorithm 0060 - Permutation Sequence (Medium)

Related Topics: Math Backtracking

## Description

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 n and k k , return the k t h k^{th} permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.

• Given k will be between 1 and n! inclusive.

Example 1:

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


Example 2:

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


## Analysis

Known set N N There is n n A digital { 1 , 2 , . . . , n } \{1,2,...,n\} Altogether n ! n! A sequence of . namely , array P n n P_n^n A sequence of . be ：

• The first one has P n 1 P_n^1 A sequence of , Others have P n − 1 n − 1 P_{n-1}^{n-1} A sequence of . namely , Each number has P n − 1 n − 1 P_{n-1}^{n-1} A sequence of . So the first k k The position of the first digit in a sequence i 1 i_1 by
i 1 = ⌊ ( k − 1 ) ÷ P n − 1 n − 1 ⌋ i_1 = \lfloor (k-1) \div P_{n-1}^{n-1} \rfloor
that Take out First digit n 1 n_1 by
n 1 = N [ i 1 ] , After taking it out ： N ∩ { n 1 } = ϕ n_1 = N \left[ i_1 \right], \quad \text{ After taking it out ：} N \cap \{ n_1 \} = \phi
namely , In the first digit from 1 1 To n − 1 n-1 share n 1 − 1 n_1-1 individual P n − 1 n − 1 P_{n-1}^{n-1} Sequence .
Then arrive at the k k A sequence also needs k 1 k_1 A sequence of , namely
k − 1 = k 1 ( m o d &ThickSpace; P n − 1 n − 1 ) k-1 = k_1 (mod \; P_{n-1}^{n-1})

• Empathy , The position of the second digit i 2 i_2 by
i 2 = ⌊ k 1 ÷ P n − 2 n − 2 ⌋ i_2 = \lfloor k_1 \div P_{n-2}^{n-2} \rfloor
Arrive at k k A sequence also needs k 2 k_2 A sequence of , namely
k 1 = k 2 ( m o d &ThickSpace; P n − 2 n − 2 ) k_1 = k_2 (mod \; P_{n-2}^{n-2})

• Final , The first i i The position of the digit i i by
i = ⌊ k i − 1 ÷ P n − i n − i ⌋ i = \lfloor k_{i-1} \div P_{n-i}^{n-i} \rfloor
Arrive at k k A sequence also needs k i k_i A sequence of , namely
k i − 1 = k i ( m o d &ThickSpace; P n − i n − i ) k_{i-1} = k_i (mod \; P_{n-i}^{n-i})

give an example n = 5 , k = 8 n=5, k=8 , be ：

num i i k − 1 = 7 k-1=7 N = { 1 , 2 , 3 , 4 , 5 } N = \{ 1, 2, 3, 4, 5 \} n = 5 n=5
1 i 1 = ⌊ 7 ÷ 4 ! ⌋ = 0 i_1 = \lfloor 7 \div 4! \rfloor = 0 k 1 = 7 &ThinSpace; m o d &ThinSpace; 4 ! = 7 k_1 = 7 \, mod \, 4! = 7 N = { 1 , 2 , 3 , 4 , 5 } N = \{ 1, 2, 3, 4, 5 \} n 1 = N [ 0 ] = 1 n_1 = N = 1
2 i 2 = ⌊ 7 ÷ 3 ! ⌋ = 1 i_2 = \lfloor 7 \div 3! \rfloor = 1 k 2 = 7 &ThinSpace; m o d &ThinSpace; 3 ! = 1 k_2 = 7 \, mod \, 3! = 1 N = { 2 , 3 , 4 , 5 } N = \{ 2, 3, 4, 5 \} n 2 = N [ 1 ] = 3 n_2 = N = 3
3 i 3 = ⌊ 1 ÷ 2 ! ⌋ = 0 i_3 = \lfloor 1 \div 2! \rfloor = 0 k 3 = 1 &ThinSpace; m o d &ThinSpace; 2 ! = 1 k_3 = 1 \, mod \, 2! = 1 N = { 2 , 4 , 5 } N = \{ 2, 4, 5 \} n 3 = N [ 0 ] = 2 n_3 = N = 2
4 i 4 = ⌊ 1 ÷ 1 ! ⌋ = 1 i_4 = \lfloor 1 \div 1! \rfloor = 1 k 4 = 1 &ThinSpace; m o d &ThinSpace; 1 ! = 0 k_4 = 1 \, mod \, 1! = 0 N = { 4 , 5 } N = \{ 4, 5 \} n 4 = N [ 1 ] = 5 n_4 = N = 5
5 i 5 = ⌊ 0 ÷ 0 ! ⌋ = 0 i_5 = \lfloor 0 \div 0! \rfloor = 0 k 5 = 0 &ThinSpace; m o d &ThinSpace; 0 ! = 0 k_5 = 0 \, mod \, 0! = 0 N = { 4 } N = \{ 4 \} n 5 = N [ 0 ] = 4 n_5 = N = 4

The final result is 13254.

## Solution C++

// Author: https://blog.csdn.net/DarkRabbit
// Problem: https://leetcode.com/problems/permutation-sequence/
// Difficulty: Medium
// Related Topics: Math Backtracking

#pragma once

#include "pch.h"

namespace P60PermutationSequence
{

class Solution
{

public:
string getPermutation(int n, int k)
{

//  altogether  n!  A sequence of
//  When the first one is confirmed , There is... In the back  (n-1)!  A sequence of
//  namely ,n The number is  n! = (n-1)! * n  A sequence of
//  be , The first k The first digit of a sequence is  k / (n-1)! + 1
//  The second is the  k % (n-1)!  A sequence of
//  Then ask for the second place  (n-2)!, And so on

vector<int> nums;
for (int i = 1; i <= n; i++)
{

nums.push_back(i);
}

int fac = 1; //  seek n-1 The factorial
for (int i = 2; i < n; i++)
{

fac *= i;
}

k--; //  Array from 0 Start

string seq;
int index;
for (int i = n - 1; i >= 0; i--)
{

index = k / fac; // k / (n-1)! + 1, Difference between subscript and value 1
seq.push_back(nums[index] + '0');
nums.erase(nums.begin() + index); //  Delete numbers that have been used

k %= fac; //  seek [n-1, n-2, ..., 1] Position in sequence
if (i > 0)
{

fac /= i; //  seek [(n-2)!, (n-3)!, ..., 0!]
}
}

return seq;
}

};
}