康拓展开

前置知识

组合数

目标

康托展开及其逆运算

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

以下称第 x 个全排列都是指由小到大的顺序。

\[X = a_n*(n-1)!+a_{n-1}*(n-2)!+...+a_1*0!\]

其中，\(a_i\) 为整数，\(0≤a_i<i,1≤i≤n\)

例如，3 5 7 4 1 2 9 6 8 展开为 98884。

因为X = 2 * 8! + 3 * 7! + 4 * 6! + 2 * 5! + 0 * 4! + 0 * 3! + 2 * 2! + 0 * 1! + 0 * 0! = 98884.

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有 8! 个，
因此第一项为 2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有 7! 个，
因此第二项为 3*7!

以此类推，直至 0*0!

康托展开的逆运算

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如n=5,x=96时：

首先用 96-1 得到95，说明x之前有95个排列.(将此数本身减去1)

用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.
用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.
用5去除2!得到2余1，类似地，这一位是3.
用1去除1!得到1余0，这一位是2.
最后一位只能是1.

所以这个数是45321

// 下面做一下验算
3 * 4! + 3 * 3! + 2 * 2! + 1 * 1! + 0 * 0! = 72 + 18 + 4 + 1 = 95
排名 95 + 1 = 96

总结

在应用过程中，注意计算准确