LeetCode 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 (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：可以想到n个数字的全排列是n！，举个例子（转的）：对于某一个n, k，比如n=4, k=17。首先知道n以下的组合数有6，2，1。那么17 = 2*6 + 2*2 + 1，

由于权值6的倍数是2，且有剩余，所以第4位（最高位）的值是从“1234”中选第3小的数，也就是3；

由于权值2的倍数是2，且有剩余，所以第3位的值是从“124”中选第3小的数，也就是4；

由于权值1的倍数是1，且没有剩余，所以第2位的值是从“12”中选第1小的数，也就是1；

最后剩下数，逆序追加到后面。

class Solution {
public:
    string remove(string s, int index, char &c) {
        c = s[index-1];
        string s1 = s.substr(0, index-1);
        string s2 = s.substr(index);
        return s1 + s2;
    }
    
    string getPermutation(int n, int k) {
        if (n > 9 || n < 1) return "";
        
        string temp = "123456789";
        int A[9] = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};  
        if (A[n-1] < k) return "";
        
        string s = temp.substr(0, n);
        if (k == 1) return s;
        if (k == A[n-1]) {
            reverse(s.begin(), s.end());
            return s;
        }
        
        string ans = "";
        char c;
        for (int i = n-2; i >= 0; i--) {
            int m = 0;
            if (k < A[i]) {
                s = remove(s, 1, c);
                ans += c;
                continue;
            }
            while (k >= A[i]) {
                k -= A[i];
                m++;
            }
            if (k == 0) {
                s = remove(s, m, c);
                ans += c;
                reverse(s.begin(), s.end());
                return ans + s;
            } else {
                s = remove(s, m+1, c);
                ans += c;
            }
        }
        
        return ans;
    }
};

LeetCode Permutation Sequence

原文：http://blog.csdn.net/u011345136/article/details/44563117