简介
对于一个集合 {1, 2, ... , n} ，其不同排列有 \(n!\) 种，将各种排列按照字典序从小到大编号（0 ～ \(n!-1\) ）。康托编码与解码旨在解决这么一个问题：给定一个排列X，它的序号是多少。或者给定一个序号，它的排列是怎么样的。
康托表达式
\(X=f(n) \cdot (n-1)! + f(n-1) \cdot (n-2)! + ... + f(1) \cdot 0!\)
编码
给定一个序列 \(a_na_{n-1}...a_1\)，\(f(i)\) 表示在该位置的右边比其小的数的个数，即 \(a_{i-1},a_{i-2}...a_1\) 中比 \(a_i\) 小的个数。例如给定一个排列2314，计算其编码步骤如下：
1. 在2右边且比2小的数的个数为有1个（1）
2. 在3右边且比3小的数的个数有1个（1）
3. 在1右边且比1小的数的个数有0个
4. 在4的右边且比4小的数的个数有0个
故排列2314的编号为 X = 1·3！+ 1·2! = 8
同理，计算可得2134的编号为6，1423的编号为4
解码
给定集合 {1,2,3,4}，给定编号13，求其排列，步骤如下：
1. 13 / 3！= 2 余 1
2. 1 / 2 ！= 0 余 1
3. 1 / 1 ！ = 1 余 0
4. 0 / 0！ = 0 余 0
商表示该位置的右边有多少个数比它大，故编号13对应的排列为3142
同理，给定编号5，可以求得排列为1432
例题
题解
该题中编号是从1开始，因此为了适用康托展开时，我们得将k减，代码如下：
class Solution {
public:
string getPermutation(int n, int k) {
//求阶乘
vector<int> factorial(n);
factorial[0] = 1;
for (int i = 1; i < n; ++i)
{
factorial[i] = factorial[i - 1] * i;
}
//k的编号从1开始，因此需自减才能适用康托表达式
--k;
string ans;
//用valid来度量order的大小，order即为前文提到的f函数
vector<int> valid(n + 1, 1);
for (int i = 1; i <= n; ++i)
{
int order = k / factorial[n - i] + 1;
for (int j = 1; j <= n; ++j)
{
//遍历到位置i
//order代表比某一个数小的数的个数且在该数左边未出现过的数的个数
order -= valid[j];
if (!order)
{
//ans代表在位置i上真实的数
ans += (j + '0');
valid[j] = 0;
break;
}
}
k %= factorial[n - i];
}
return ans;
}
};