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.

solution1

这个回溯的方法会超时

  class Solution(object):
      def getPermutation(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: str
          """
          res = []
          substr = ""
          self.backtracking(n,res, substr)
          # 注意返回的res[k-1]而不是res[k]
          return res[k-1]
      def backtracking(self, n, res, substr):
          if len(substr) == n:
              res.append(substr)
              return
          for i in range(1, n+1):
              if str(i) in substr:
                  continue
              self.backtracking(n, res, substr+str(i))

solution2

思路:

同样先通过举例来获得更好的理解。以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次。所以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

class Solution {
public:
    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;
    }
};

https://www.cnblogs.com/grandyang/p/4358678.html

  class Solution(object):
      def getPermutation(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: str
          """
          res = ""
          num = "123456789"
          # 先求一个阶乘函数或者数组
          factorial={0:1}
          for i in range(1, n):
              factorial[i] = factorial[i-1] * i
          for i in range(n, 0, -1):
              j = k / factorial[i-1]
              k = k % factorial[i-1]
              res += num[j]
              num = num.replace(num[j], "")
              i -= 1
          return res