60. Permutation Sequence

• 方法1: backtracking (TLE)
• 方法2: calculate number of permutation given each MSP
• • 思路：
  • 易错点：
  • code

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:

"123"
"132"
"213"
"231"
"312"
"321"
           

Given n and k, return the kth 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"
           

方法1: backtracking (TLE)

首先想到暴力dfs找到所有n！个解然后取第k个，但是肯定会超时。

方法2: calculate number of permutation given each MSP

思路：

思路：给定ｎ个数字让求第k个序列．ｎ个数字总共的全排列最多有n!个，并且全排列有个规律．

给定一个n，以１开头的排列有(n-1)!个，同样对２和３也是，所以如果k小于等于(n-1)!，那么首位必为１，因为以１开头的全排列有(n-1)!个．

同样如果k大于(n-1)!，那么第一个数就应该为(k-1)/(n-1)! + 1．这样找到了首位数字应该是哪个，剩下了(n-1)个数字，我们只需要再重复上面的步骤，不断缩小k即可．

原文：https://blog.csdn.net/qq508618087/article/details/51635302

通过举例来获得更好的理解。以n = 4，k = 9为例：

1234
1243
1324
1342
1423
1432
2134
2143
2314  <= k = 9
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
           

最高位可以取{1, 2, 3, 4}，而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。

而对于以2开头的6个数字而言，k = 9是其中的第k’ = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s1为{1, 3, 4}中的第k’/(2!)+1 = 2个，即s1 = 3。

对于以23开头的2个数字而言，k = 9是其中的第k’’ = k’%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.

对于以231开头的一个数字而言，k = 9是其中的第k’’’ = k’’/(1!)+1 = 1个。s[3] = 4

那么我们就可以找出规律了:

a1 = k / (n - 1)!

k1 = k

a2 = k1 / (n - 2)!

k2 = k1 % (n - 2)!

…

an-1 = kn-2 / 1!

kn-1 = kn-2 % 1!

an = kn-1 / 0!

kn = kn-1 % 0!

原文：https://blog.csdn.net/fuxuemingzhu/article/details/80658810

?王：https://www.youtube.com/watch?v=xdvPD1IiyUM

易错点：

1. 数字本身和index之间相差1，为了防止混淆，永远转化成index 来keep track（见comment）
2. vector factorial(n, 1) , 这个table的ith number = i ！，最后一位是（n-1）！，因为本来也没有必要算n！

code

class Solution {
public:
    string getPermutation(int n, int k) {
        string result;
        if (n == 0 || k == 0) return result;
        string nums = "123456789";
        
        vector<int> factorial(n, 1);
        for (int i = 1; i < n; i++){
            factorial[i] = factorial[i - 1] * i;
        }        
        // printVector(factorial);
        
        // 这里--k是因为如果求第9/9个结果，我们希望index的是8
        // k的含义转变为要找string的index，0-based
        --k;
        
        for (int i = n; i > 0 ; i --){
            // 我们要找的结果在第k/factorial[i - 1] + 1个block当中，该block代表的数字是
            // k/factorial[i - 1] + 1
            // 其在string nums中的index是k / factorial[i - 1]
            // j 是index，所以直接取k/factorial[i - 1] + 1
            int j = k / factorial[i - 1];
            // k每次被更替成余数，“在该block中index = k 的数是多少？”
            k = k % factorial[i - 1];
            result.push_back(nums[j]);
            // 注意函数定义erase（position，length）
            nums.erase(j, 1);
        }
       
        return result;   
    }
    
    void printVector(vector<int> & a){
        for (int b: a){
            cout << b << " ";
        }
        cout << endl;
    }
};