【概述】

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩，在组合数学中，其解决的是当前排列在全排列中的名次问题。

简单来说，给定一个 n 位数的全排列，可根据康托展开公式确定其应是字典序中的第几个排列。

由于康托展开计算的是某个全排列方式在该全排列集合中的字典序，其映射关系是唯一的，而且单调，因此映射关系是可逆的，故而当给定一个全排列的所有字符，以及某个字典序编号，可以利用逆康托展开得到相应的那个全排列。

【康托展开】

对于康托展开，有公式：，其中 a[i] 表示原排列中，排在下标 i  后的，比下标 i 的字符还小的字符个数

通过公式算出来的康托展开值，是指当前序列在之前的全排列的个数，因此 X+1 即为该序列在全排列中的次序。

以序列 {3,2,5,4,1} 为例：

• 对于 3：比 3 小的有 1、2，所以 3 是第 2 小的，X+=2*(5-1)!
• 对于 2：比 2 小的有 1，所以 2 是第 1 小的，X+=1*(4-1)!
• 对于 5：比 5 小的有 1、2、3、4，但由于 2、3 已经出现过了，所以目前 5 是第 2 小的，X+=2*(3-1)!
• 对于 4：比 4 小的只剩 1，所以 X+=1*(2-1)!
• 对于 1：已经是最小的，X+=0*(1-1)!

因此，X=2*(5-1)!+1*(4-1)!+2*(3-1)!+1*(2-1)!+0*(1-1)!+1=48+6+4+1+0+1=60

因此，序列｛3,2,5,4,1｝在由数 1~5 组成的全排列中的次序是 60

int a[N];
int fac[N];
void getFactor(int n) { //计算阶乘
    fac[0]=1;
    for(int i=1; i<=n; i++)
        fac[i]=fac[i-1]*i;
}
int contor(int n) { //康托展开
    int X=0;
    for(int i=1;i<n;i++){
        int cnt=0;
        for(int j=i+1;j<=n;j++)
            if(a[j]<a[i])
                cnt++;
        X+=cnt*fac[n-i];
    }
    return X+1;
}
int main() {
    int n;
    scanf("%d",&n);
    getFactor(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int res=contor(n);
    printf("%d\n",res);
    return 0;
}

【逆康托展开】

康拖展开是从序列到自然数的映射且是可逆的，那么逆康拖展开便是从自然数到序列的映射，简单来说，逆康托展开，就是给出 1~n 的数列，求出排名第 x 的数

以序列 {1,2,3,4,5} 为例，求第 10 的序列：

有：X=10，X-1=9，那么：

• 第一个数：9/(5-1)!=0…9，说明比第一个数小的、没有出现过的数不存在，因此第一个数是：1
• 第二个数：9/(4-1)!=1…3，说明比第二个数小的、没有出现过的数有 1 个，因此第二个数是：3
• 第三个数：3/(3-1)!=1…1，说明比第三个数小的、没有出现过的数有 1 个，因此第三个数是：4
• 第四个数：1/(2-1)!=1…0，说明比第四个数小的、没有出现过的数有 1 个，因此第四个数是：5
• 第五个数：0/(1-1)!=0…0，说明比第五个数小的、没有出现过的数不存在，因此第五个数是：2

因此，第 10 的序列为 {1,3,4,5,2}

int fac[N];
bool vis[N];
void getFactor(int n) { //计算阶乘
    fac[0]=1;
    for(int i=1; i<=n; i++)
        fac[i]=fac[i-1]*i;
}
vector<int> revContor(int n, int X) {//逆康托展开
    memset(vis,false,sizeof(vis));
    vector<int> res(n,-1);
    X--;

    int residue=X;//除数
    for (int i=0; i<=n-1; i++) {
        int cnt=residue/(fac[n-i-1]);
        residue=residue%(fac[n-i-1]);

        for(int j=1;j<=n;j++) {
            if (!vis[j]) {
                if(!cnt){
                    vis[j]=true;
                    res[i]=j;
                    break;
                }
                cnt--;
            }
        }
    }
    return res;
}
int main() {
    int n,num;
    scanf("%d%d",&n,&num);
    getFactor(n);
    vector<int> res=revContor(n,num);
    for(int i=0;i<res.size();i++)
        cout<<res[i];
    return 0;
}

【例题】

• Uim的情人节礼物·其之弐（洛谷-P2524）(康托展开)：点击这里
• Cow Line（洛谷-P3014）(康托展开+逆康托展开)：点击这里
• 第K个幸运排列 （51Nod-1635）(逆康托展开+dfs)：点击这里

今天的文章组合几何CMO_康托数学史讲义分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。