60. Permutation Sequence.md

title	toc	date	tags	top
60. Permutation Sequence	false	2017-10-30	Leetcode Math Backtracking	60

题目

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.

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"

分析

最直接的方法是用backtracking把每一个$k^{th}$排列算出来。

// 初始化chosen vector, 即1...n
void initialize(vector<int>& v, int n){
    for (int i=1; i<=n; i++)
        v.push_back(i);
}
    
// next_k: 记录了当前的k
// permuation: kth permuation
// v: 余下的可以选择的数字
// res: result to return
bool getPermutationHelper(int n, int k, int& next_k, 
            string& permutation, vector<int>& v, string& res){
    if (!v.size()){
        // base case
        next_k += 1;
        if (next_k == k+1){
            res = permutation;
            return true;
        }
    }else{ 
        for(vector<int>::iterator iter=v.begin(); 
                    iter!= v.end(); iter++){
            // choose
            int s = *iter;
            permutation.append(to_string(s));
            v.erase(iter);
            // explore
            bool finished = getPermutationHelper(n, k, next_k, permutation, v, res);
            if (finished) return true;
            // unchoose
            permutation.pop_back();
            v.insert(iter, s);
        }
    }
    return false;
}

//Given n and k, return the kth permutation sequence.
string getPermutation(int n, int k) {
    string res, permutation;
    int next_k = 1 ;
    vector<int> v;
    initialize(v, n);
    getPermutationHelper(n, k, next_k, permutation, v, res);
    return res;
}

可惜的这种方法超时了。

另一种解决方案，直接从数学的角度出发。

因为$n$个不同的数字可以组成$n!$个排列，那么首位(第一个数字)确定的排列都有$(n-1)!$种不同的可能性，而且这些序列都根据首位的大小进行了分组，1...是最小的$(n-1)!$个排列，2...是第$(n-1)!+1$到$2(n-1)!$个排列，那么现在只需要计算$k$中有几个$(n-1)!$就可以确定首位的数字，同样可以通过这样的方法来确定$k^{th}$排列中第2位、第3位……数字。此外，由于列表下标从0开始，所以$k$要减去1。

通过举例来获得更好的理解。以$n = 4，k = 9$为例，其所有排列为：

1 + (permutations of 2, 3, 4)
2 + (permutations of 1, 3, 4)
3 + (permutations of 1, 2, 4)
4 + (permutations of 1, 2, 3)

最高位可以取{1, 2, 3, 4}，而每个数重复$3! = 6$次。所以第$k=9$个排列的$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$次。所以$s[1]$为${1, 3, 4}$中的第$k'/(2!)+1 = 2$个，即$s[1] = 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$.

// x的阶乘 x!=1*2*..*x
int factorial(int x){
    int num = 1;
    for(int i = 1; i <= x; i++) num *= i;
    return num;
}
    
    
// position: 求取的第position位
// res: result to return
void getPermutationHelper(int k, int position, 
            vector<char>& num, string& res){
    if (position < 0){
        return;
    } else{
        int s = factorial(position);
        int index = k/s;
        res.push_back(num[index]);
        num.erase(num.begin() + index);
        getPermutationHelper(k%s, position-1, num, res);
    }        
}
    
string getPermutation(int n, int k) {
    string res;
    vector<char> num;
    for (int i=1; i<=n; i++)
        num.push_back(i+'0');
    getPermutationHelper(k - 1, n - 1, num, res );
    return res;
};

递归版本，把factorial写成vector形式以后简洁了很多，对于factorial的计算以空间换时间：

string getPermutation(int n, int k) {
    string ret;
    vector<int> factorial(n, 1);
    vector<char> num(n, 1);

    for(int i = 1; i < n; i++) 
        factorial[i] = factorial[i-1] * i;
    for(int i = 0; i < n; i++)
        num[i] = (i + 1) + '0';
    k--;
    for(int i = n; i >= 1; i--) {
        int j = k / factorial[i - 1];
        k %= factorial[i - 1];
        ret.push_back(num[j]);
        num.erase(num.begin() + j);
    }
    return ret;
}