首页 > itarticle > 康托展开和逆康托展开

康托展开和逆康托展开

admin 11月 14, 2020 0

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

康托展开

康托展开可以在非常短的时间内计算出某个全排列在所有长度相同的全排列中的顺序，其基本思想为：

从左至右计算出当前位所对应的贡献，将每一位的贡献累加即可计算出这个全排列的顺序，其贡献为 $a_i * (n-i)!+1(1 leq i leq n)$ ,其中 $a_i $ 表示第 $i$ 位后面有多少位的值小于当前位的值。

举例说明：$5, 3, 2, 4, 1$ ，其顺序为：
$$
4*(5-1)!+2*(5-2)!+1*(5-3)!+1*(5-4)!+0*(5-5)!+1=112
$$
所以其是第$112$个全排列，至于最后为什么加$1$，因为对于全排列 $1,2,3,4,5$ ，计算出来的值为：
$$
0*(5-1)!+0*(5-2)!+0*(5-3)!+0*(5-4)!+0*(5-5)!=0
$$
其对应的顺序为$0$，所以需要$+1$来修正这个顺序。

代码如下：

1
2
3
4
5
6
7
8
9
10
 
void (){
    ll sum=1,fac=1;
    for(int i=n-1;i>0;i--){
        fac*=(n-i);
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j]) sum+=fac;
        }
    }
    printf("%lldn",sum);
}

至于为什么这样算，略……（毕竟证明确实不算难）

逆康托展开

逆康托展开与康托展开相对应，求第 $i$ 个全排列的值。

其求解过程与康托展开类似，也是从左至右一位一位进行求解，但过程相对康托展开有些繁琐：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void inverse_cantor(){
    ll fac=1,num;
    k--;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<n;i++) fac*=i;
    for(int i=1;i<=n;i++){
        num=k/fac;
        k%=fac;
        if(n-i) fac/=(n-i);
        for(int j=1;j<=n;j++){
            if(num==0 && !vis[j]){
                printf("%d ",j);
                vis[j]=1;
                break;
            }
            if(!vis[j]) num--;
        }
    }
    printf("n");
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能