class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        allFactorial = [1, 1]
        for i in range(2, n+1):
            allFactorial.append(allFactorial[-1]*i)

        s, k, res = list(range(1, n+1)), k-1, ""
        for i in range(len(s)-1, -1, -1):
            res += str(s[k // allFactorial[i]])
            del s[k // allFactorial[i]]
            k %= allFactorial[i]
        return res


"""
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"

举个例子，n = 4：
全排列：
1234 → 1243 → 1324 → 1342 → 1423 → 1432 →
2134 → 2143 → 2314 → 2341 → 2413 → 2431 →
3124 → 3142 → 3214 → 3241 → 3412 → 3421 →
4123 → 4132 → 4213 → 4231 → 4312 → 4321
规律：
前缀1出现的次数：(len([1, 2, 3, 4])-len([1]))!：3!： 6
前缀12出现的次数：(len([1, 2, 3, 4])-len([1, 2]))!：2!： 2
...
总结：
(n-m)!，其中n代表数组长度，m为前缀长度。
比如，k = 9：
当前列表为[1, 2, 3, 4]
当前全排列前缀为1的元素出现6次；
当前答案的前缀一定为2（[1, 2, 3, 4][9 // 6]）：
剩下[1, 3, 4]：
当前全排列前缀为1的元素出现了2次：
当前答案的前缀一定为3（[1, 3, 4][3 // 2]）：
剩下[1, 4]：
...

"""