康托展开是什么
康托展开用于求一个排列在所有 1~n 的排列间的字典序排名，它是一个从排列到自然数的双射，常用于构建哈希表时的空间压缩。通俗点讲，康托展开可以求解一个排列的序号，比如：12345 在 1~5 的所有的排列中字典序为 1 ，12354 的序号为 2 ，以此类推。因为康托展开是双射，所以同样存在逆康托展开，即从排名倒推出排列。
康托展开原理
1.何为字典序
在数学中，字典序是基于字母顺序排列的单词按字母顺序排列的方法。在全排列中，它们的字典序则是基于数字大小来进行比较的，对于数字 1、2、3......n 的排列，不同排列的先后关系是从左到右逐个比较对应的数字的大小来决定。比如 4 的排列 [2，3，1，4] 和 [2，3，4，1] ，因为第三位出现不同，且 1＜4 ，所以 [2，3，1，4] 排在 [2，3，4，1] 前面。
2.如何计算
我们拿长度为 5 的排列 [2，5，3，4，1] 来举例子：
- 第一位是 2 ，比 2 小且还没用过的数字有 1 ，所以可以令 1 为开头，后面四位任意排列，共有
1×4!种排列比当前小 - 固定第一位，看第二位 5 ，比 5 小且还没用过的数字有 1、3、4 ， 所以可以分别令第二位为1、3、4，后面三位任意排列，共有
3×3!种排列比当前小 - 固定一二位，看第三位 3 ，比 3 小且还没用过的数字有 1 ，所以可以令第三位为 1 ，后面二位任意排列，共有
1×2!种排列比当前小 - 固定一到三位，看第四位 4 ，比 4 小且还没用过的数字是 1 ，所以可以令第四位为 1 ，后面一位任意排，共有
1×1!种排列比当前小
按照上面步骤的统计，我们就可以得出比排列 [2，5，3，4，1] 的字典序小的排列一共有 1×4!+3×3!+1×2!+1×1!=45 个，所以我们就能知道排列 [2，5，3，4，1] 是第 46 个排列，即字典序为 46 。可以注意到，我们是从左往右依次按位去计算，每位用到的数字一定是比当前位小且前面没出现过的数字，否则就会统计重复。
3.原理总结
根据上面的步骤，我们可以发现康托展开的原理很简单。设有排列 $p=a_1a_2a_3...a_n$ ，那么对任意字典序比 p 小的排列，一定存在 i ，使其前 i-1（1≤i＜n） 位与 p 对应，第 i 位比 $p_i$ 小，后续的位随意组合。于是对于任意的 i ，满足条件的排列数就是在后 n-i+1 位中选出一个比 $p_i$ 小的数 $a_i$，并将剩下 n-i 个数任意排列的方案数，即为 $A_i · (n-i)!$ （$A_i$ 表示 $p_i$ 后面比 $p_i$ 小的数的个数）。所以我们遍历所有的位，即可得到总方案数 $\sum_{i=1}^{n-1} A_i · (n-i)!$ ，再加上 1 即为排名。
代码实现
根据上面的原理总结，问题就转化成如何求 $A_i$ 了，显然可以用 $O(n^2)$ 的方式来求：
const int maxn = 11;
// 存储1-10阶乘
ll fact[maxn] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
ll P[maxn], A[maxn];
// 函数传入的参数是1-n的排列
ll cantor(ll P[], int n)
{
ll ans = 1;
for(int i = 1; i <= n; ++i)
for(int j = i+1; j <= n; ++j)
if(P[j] < P[i])
A[i]++; // 统计第i位后面有多少比它小的
for(int i = 1; i < n; ++i)
ans += A[i] * fact[n-i];
return ans;
}这个复杂度其实很够了，毕竟 21! 就已经超过 long long 范围了，很多时候康托展开也就是在这个规模下进行。如果再大，就需要上高精度或者需要取模了。当然，优化也不难，注意到我们每次要用到当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就可以了，可以优化到 O(NlogN) ：
const int maxn = 11;
// 存储1-10阶乘
ll fact[maxn] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
ll P[maxn], A[maxn], tree[maxn];
// lowbit操作
ll lowbit(ll x){ return x & -x; }
// 前n项和
ll query(ll x)
{
ll ans = 0;
for(int i = x; i >= 1; i -= lowbit(i))
ans += tree[i];
return ans;
}
// 单点更新
void update(ll idx, ll x)
{
for(int i = idx; i < maxn; i += lowbit(i))
tree[i] += x;
}
// 函数传入的参数是1-n的排列
ll cantor(ll P[], int n)
{
ll ans = 1;
// 倒着来统计，保证统计的是当前位之后出现的比它小的数字
for(int i = n; i >= 1; --i) {
A[i] = query(P[i]);
update(P[i],1);
}
for(int i = 1; i < n; ++i)
ans += A[i] * fact[n-i];
return ans;
}应用例题
康托展开的一个典型的应用是八数码问题
逆康托展开原理
与康托展开相对应的是逆康托展开，即求指定排名的排列。因为康托展开是双射关系，所以我们可以通过把上面的步骤倒过来推出排列。
1.举个栗子
还是以上面的栗子，假设现在有一个 1-5 的排列，我们可以知道，最大的排列就是 [5，4，3，2，1] ，根据康托展开，我们可以列出式子 4×4!+3×3!+2×2!+1×1! 。根据数学我们可知， 4! 是严格大于 3×3!+2×2!+1×1! ，所以可以认为对于长度为 5 的排列，假设有 x 个比他小的排列，$\lfloor \frac{x}{4!} \rfloor$ 就是有多少个数比第一位数字小
假设有个长度为 5 的排列序号是 46 ，我们可以通过上面的数学运算倒推回他是哪一个排列：
- 首先 46-1 = 45 ，代表有45个排列比它小，$\lfloor \frac{45}{4!} \rfloor$ = 1，有一个数比第一位数小，所以第一位是 2
- 让
2.数学推算
代码实现
康托展开应用
个人感悟
由于康托展开可以使得一长串数字的排列化为排名，可以用于hash也就是散列表的储存，此时储存就不需要存一大串数字，而是直接储存它的排名，需要输出时再逆康托展开即可。
参考资料
版权属于：PCsky
本文链接：http://hyouka.club/index.php/archives/162/
转载时须注明出处及本声明