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

详解"/>

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

文章目录

• • • • 康拓展开
      • 运用
      • 板子
      • 逆康托展开
      • 板子

康拓展开

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

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

运用

对于 a a a数组这个排列，其康拓展开式如下
X = A [ 0 ] ∗ ( n − 1 ) ! + A [ 1 ] ∗ ( n − 2 ) ! + … A [ n ] ∗ 0 ! X = A[0]*(n-1)!+A[1]*(n-2)!+…A[n]*0! X=A[0]∗(n−1)!+A[1]∗(n−2)!+…A[n]∗0!
A [ i ] A[i] A[i]为 i i i后比 a [ i ] a[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 53241 53241是 5 5 5的全排列中编号为 111 111 111的数
用 111 111 111得到 53241 53241 53241的过程如下：
用 111 / 4 ! = 4 111 / 4! = 4 111/4!=4余 15 15 15，说明比首位小的数有 4 4 4个，所以首位为 5 5 5，余数继续辗转。

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

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

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

用 0 / 0 ! = 0 0 / 0! = 0 0/0!=0余0，说明在第五位之后小于第五位的数有 0 0 0个，所以第五位为 1 1 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);//移除数}
}