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;
    }
};