康托展开 & 逆康托展开

定义

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。

设有$n$个数$（1,2,3,4,\dots ,n）$，组成不同$n!$ 种的排列组合，其康托展开唯一且最大约为$n!$

康托展开表示的就是当前排列在$n$个不同元素的全排列中的名次。

时间复杂度$O(n^2)$

适用范围

搜索，动态规划中常常用一个数字来表示一种状态，大大降低空间复杂度

公式

$X=a_1\times(n−1)!+a_2\times(n−2)!+⋯+a_n\times0!$

$X$ 代表当前排列在全排列中的排名

$a_i$ 代表当前数是数列中未出现的数中第几小的 从0开始计数，0是第一小的数

例如 $ 4,2,3 ,1 $

$4$ 是当前数列中未出现的数中第$3$ 小的，$X += 3*(4-1)!$

$2$ 是当前数列中未出现的数中第$1$ 小的，$X += 1*(4-2)!$

$3$ 是当前数列中未出现的数中第$1$ 小的，$X+=1*(4-3)!$ ,因为$2$ 已经输出过了，所以不算

$1$ 是当前数列中未出现的数中第$0$ 小的，$X += 0*(4-4)!$

这要就求出了$4,2,3 ,1$ 所唯一对应的在全排列中的名次$X = 22$

• 注意到我们每次要用到 当前有多少个小于它的数还没有出现
• 这里用树状数组统计比它小的数出现过的次数就可以了，可以优化到$O(n\log{n})$

代码

先预处理阶乘

void init() {
    fact[0] = 1;
    for(int i = 1;i <= 9; ++i) fact[i] = fact[i - 1] * i;
    // 递推求阶乘
}
// 或者直接打表
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

$cantor$函数

int cantor(int a[],int n) {
    int res = 0;
    for(int i = 0;i < n; ++i) {
        int cnt = 0;
        for(int j = i + 1;j < n; ++j) if(a[j] < a[i]) cnt ++;
        // 找到a[i]是当前数列中未出现的数中第几小的
        // 从1开始，即1-n的全排列
        // 从0开始，就变成了0-n的全排列，记得变通
        res += cnt * fact[n - i - 1];// 累加值
    }
    return res + 1;// 如果输出的是排名就要 + 1，如果是hash值可以直接返回 res
}

逆康托展开

因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。

可以通过类似上面的过程倒推回来。

首先把排名$X$ 减去$1$ ，变成以$0$ 开始的排名

例如求 $1,2,3,4$ 的全排列序列中，排名第$22$ 的序列是什么

$22 - 1 = 21$ ， $21$ 代表着有多少个排列比这个排列小

第一个数 $a[1]$

$\lfloor{21/(4-1)!}\rfloor = 3$ 比$a[1] $ 小且没有出现过的数有$3$ 个，$a[1]=4$

$X=X\mod3\times(4-1)!=3$

第二个数$a[2]$

$\lfloor{3/(4-2)!}\rfloor=1$ 比$a[2]$ 小且没有出现过的数有$1$ 个，所以$a[2]=2$

$X=X\mod1\times(4-2)!=1$

第三个数$a[3]$

$\lfloor{1/(4-3)!}\rfloor=1$ 比$a[3]$ 小且没有出现过的数有$1$ 个，所以$a[3]=3$

$X=X\mod1\times(4-3)!=0$

第四个数$a[4]$

$\lfloor{0/(4-4)!}\rfloor=0$ 比$a[4]$ 小且没有出现过的数有$0$ 个，所以$a[4]=1$

最终得到数列$4,2,3,1$

代码

vector<int> incantor(int x,int n) {
    x--;// 得到以0开始的排名
    vector<int> res(n);// 保存数列答案
    int cnt;
    bool st[10];// 标记数组
    memset(st,0,sizeof st);
    for(int i = 0;i < n; ++i) {
        cnt = x/fact[n - i - 1];// 比a[i]小且没有出现过的数的个数
        x %= fact[n - i - 1];// 更新 x
        for(int j = 1;j <= n; ++j) {// 找到a[i]，从1开始向后找
            if(st[j]) continue;// 如果被标记过，就跳过
            if(!cnt) {// 如果cnt == 0说明当前数是a[i]
                st[j] = 1;//标记
                res[i] = j;// 第i位是j
                break;
            }
            cnt --;// 如果当前不是0，就继续往后找
        }
    }
    return res;// 返回答案
}