康托展开与逆康托展开详解

康拓展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次，因此是可逆的。
例如$312$
当我们把$3$的全排列全部打出来并按从大到小排列编号后，如下图

我们可以得到$312$的编号是$4$，而康拓展开，就是帮助我们求到这种次序编号，以便来进行标记

运用

对于$a$数组这个排列，其康拓展开式如下
$$X=A[0]\ast (n-1)!+A[1]\ast (n-2)!+\dots A[n]\ast 0!$$
$A[i]$为$i$后比$a[i]$小的数的数量

板子

inline int contor(int *x){
    int sum = 0;
    for(int i = 0; i < n; i ++ ){
        int num = 0;
        for(int j = i+1; j < n; j ++){
            if( x[i] > x[j] )
                num++;
        }
        sum += num*jc[n-i-1];//阶乘
    }
    return sum;
}

逆康托展开

听名字就知道，就是倒过来，用编号还原排列
举个例子，
$53241$是$5$的全排列中编号为$111$的数
用$111$得到$53241$的过程如下：
用 $111/4!=4$余$15$，说明比首位小的数有$4$个，所以首位为$5$，余数继续辗转。

用$15/3!=2$余$3$，说明在第二位之后小于第二位的数有$2$个，所以第二位为$3$，余数继续辗转。

用 $3/2!=1$余$1$，说明在第三位之后小于第三位的数有$1$个，所以第三位为$2$，余数继续辗转。

用$1/1!=1$余$0$，说明在第四位之后小于第四位的数有$1$个，所以第四位为$4$（2,3,5都取过了），余数继续辗转。

用$0/0!=0$余0，说明在第五位之后小于第五位的数有$0$个，所以第五位为$1$，结束n次循环。

板子

void ni_contor(int x, int n){
    vector<int> v;//存放可以选的数
    vector<int> a;//求排列
    for(int i = 1; i <= n; i ++)
        v.push_back(i);
    for(int i = n; i > 1; i --){
        int p = x % jc[i-1];
        int q = x % jc[i-1];//阶乘
        x = p;
        sort(v.begin(), v.end());//排序
        a.push_back(v[q]);//选剩余数中第q+1个数为当前位
        v.erase(v.begin()+t);//移除数
    }
}

最后

以上就是知性鼠标为你收集整理的康托展开与逆康托展开详解的全部内容，希望文章能够帮你解决康托展开与逆康托展开详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。