题目：
难度：Middle
相关话题：数学、回溯算法
给出集合 [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<=9，在这个范围内可以使用暴力解(回溯)，但肯定不是最优解，一旦n>=12耗时就很可怕了。
这里最优解使用的是Cantor expansion 康拓逆展开。
什么是康拓展开和康拓逆展开呢，维基百科写的很清楚，这里也简单说一下。
例如，2431有多少种排列方式会比它小的，那么我们的计算方式是：
1 * 3! + 2 * 2! + 1 * 1! + 0 * 0! = 11
解释：
第一个数2，比它小的有1个，后续能排列数量有3!
第二个数4，减去它之前的2，比它小的还有2个，后续能排列数量有2!
第三个数3，减去它之前的2，比它小的还有1个，后续能排列数量有1!
…
这就是康拓展开，那么康拓逆展开就是反过来。
例如 n=4, k=12
那么首先前面有k-1=11个排序是比当前小的。
第一个数字，11 除以 3!，结果为1余5，说明有1个比它小，因此第一个数字是2；
第二个数字，5 除以 2!，结果为2余1，说明有2个比它小，因为上面2已经使用了，因此这里是4；
第三个数字，1 除以 1!，结果为1余0，说明有1个比它小，上面2已经使用了，因此这里是3；
第四个数字，0 除以 0!，0为分母无法计算，这里是最后一个数字1。
时间复杂度是O(n)。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
function factorial(n){
if(n===0)return 0
let m=1
for(let i=n;i>=1;i--){
m*=i
}
return m
}
let cache=[1,2,3,4,5,6,7,8,9]
let res=''
k-=1
for(let i=n-1;i>=0;i--){
let f=factorial(i)
let chooseID=f===0? 0 : Math.floor(k/f)
res+=cache[chooseID]
cache.splice(chooseID,1)
k=k % f
}
return res
};
扩展阅读：