跳转至

60. Permutation Sequence

Leetcode Math Backtracking

题目

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