# Permutation Sequence

## Permutation Sequence

[原题链接](https://leetcode.com/problems/permutation-sequence/)

### 描述

> 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 *k*th permutation sequence.

### 例子

> Input: n = 3, k = 3 
>
> Output: "213"
>
> Input: n = 4, k = 9 
>
> Output: "2314"

### Note

> * Given *n* will be between 1 and 9 inclusive.
> * Given *k* will be between 1 and *n*! inclusive.

### 解法一

```cpp
class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "", res = "";
        vector<int>factorial(n + 1, 1);
        int sum = 1;
        for(int i = 1; i <= n; i++){
            s.push_back(i + '0');
            sum *= i;
            factorial[i] = sum;
        }
        k--;
        for(int i = 1; i <= n; i++){
            int index = k / factorial[n - i];
            res.push_back(s[index]);
            s.erase(s.begin() + index);
            k %= factorial[n - i];
        }
        return res;
    }
};
```

[出处](https://leetcode.com/problems/permutation-sequence/discuss/696910/C%2B%2B-or-100-time-space-efficient-or-Iterative-Solution-or-Detailed-Explanation-with-Example)

The approach is mathematical. The idea is to keep selecting a digit and eliminating it from further selection based on value of K.

For example:

**Given, N = 4, K = 9**

There are 6 numbers starting with 1: 1234, 1243, 1324, 1342, 1423, 1432\
There are 6 numbers starting with 2: 2134, 2143, 2314, 2341, 2413, 2431\
Similarly, there are 6 numbers starting with 3 and 6 numbers starting with 4.

**This is because when we have chosen one place out of 4 places (as N=4), there are 3 places remaining to be filled and those 3 places can be filled in 6 ways or (N-1)! ways.**

So, we have to keep identifying which digit to choose.

Initially, we have to choose a digit from **{1,2,3,4}.**

Since K = 9, meaning it belongs to second set of six numbers and hence, would begin with 2.

**Now, first place is chosen as 2 and output string becomes "2".**\
**This means we have eliminated 6 choices starting with 1 (1234, 1243, 1324, 1342, 1423, 1432).**

Now, K would be updated as **K = 9 - 6 = 3.**

We now have to identify remaining 3 places with the digits **{1,3,4}** and with **K = 3.**

There are 2 numbers starting with 1: 134, 143\
There are 2 numbers starting with 3: 314, 341\
There are 2 numbers starting with 4: 413, 431

This is because when we have chosen one place out of 3 available places, there are 2 places remaining to be filled and those 2 places can be filled in 2 ways.

**Since, K = 3, meaning it belongs to second set of two numbers and hence, answer would be appended with "3" and output string becomes "23".**\
**This means we have eliminated 2 choices starting with 1 (134, 143).**

Now, K would be updated as K = 3 - 2 = 1.

We now have to identify remaining 2 places with the digits **{1,4}** with **K = 1.**

There is 1 number starting with 1: 14\
There is 1 number starting with 4: 41

This is because when we have chosen one place out of 2 available places, there is only 1 place remaining to be filled and that 1 place can be only be filled in 1 ways.

**Since, K = 1, meaning it belongs to first set of one number and hence, answer would be appended with "14" and output string becomes "2314".**

**Therefore, final answer becomes "2314".**

### 解法二

```cpp
class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "";
        for(int i = 1; i <= n; i++) s.push_back(i + '0');
        while(--k) next_permutation(s.begin(), s.end());
        return s;
    }
};
```

[next\_permutation](http://cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation)

### 解法三 backtracking

```cpp
class Solution {
public:
    string getPermutation(int n, int k) {
        string s = "", res = "";
        for(int i = 1; i <= n; i++) s.push_back(i + '0');
        string path = s;
        int count = 0;
        DFS(s, 0, count, n, k, path, res);
        return res;
    }
    
    void DFS(string& s, int pos, int& count, int n, int k, string& path, string& res){
        if(count >= k || pos == n){
            if(++count == k) res = path;
            return;
        }
        for(int i = 0; i < n; i++){
            if(s[i] == '0') continue;
            path[pos] = s[i];
            s[i] = '0';
            DFS(s, pos + 1, count, n, k, path, res);
            s[i] = path[pos];
        }
    }
};
```