本文主要是介绍康托展开（Cantor Expansion），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【康托展开简介】
康托展开（Cantor Expansion）是一种特殊的哈希函数，是一个相对快速的判重方法，其时间复杂度为O(n^2)，其中 n 是集合中元素的个数。康托展开能够判重，依据的是一个集合各元素产生的全部排列中各个排列的位序 id。而位序 id 的计算公式如下：
其中，a[i] 的值为某个排列中第 i 位右边各位中字典序小于第 i 位的字符的个数，且0≤a[i]＜i，1≤i≤n。
利用此公式时，约定长度为n的某个排列，其下标由左至右依次为 n~1。
【康托展开习题】
例如，判断 7698 是 {6, 7, 8, 9} 的全排列中的第几大数（位序）的过程如下：
（0）为了利用上述公式，约定排列 7698 的下标从左至右依次为4, 3, 2, 1 (下标从1开始)，a[i] 的值为某个排列中第 i 位右边各数中小于第 i 位的数的个数。
（1）在排列 7698 中，第4位为7，其右边各位比它小的数有a[4]=1个，为6。根据上文公式，贡献1×(4-1)!=6。
（2）在排列 7698 中，第3位为6，其右边各位比它小的数有a[3]=0个。根据上文公式，贡献0×(3-1)!=0。
（3）在排列 7698 中，第2位为9，其右边各位比它小的数有a[2]=1个，为8。根据上文公式，贡献1×(2-1)!=1。
（4）在排列 7698 中，第1位为8，其右边各位比它小的数有a[1]=0个。根据上文公式，贡献0×(1-1)!=0。
求和，得 1×(4-1)!+0×(3-1)!+1×(2-1)!+0×(1-1)!=6+0+1+0=7。即比排列 7698 位序小的排列有 7 个，也即排列 7698 的位序为8。
【康托展开代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=100;
int f[maxn];void fact(int n) {f[0]=1;for(int i=1; i<=n; i++)f[i]=f[i-1]*i;
}int cantor(string s){int ans=1;int len=s.length();for(int i=0;i<len;i++){int cnt=0;for(int j=i+1;j<len;j++){if(s[i]>s[j]) cnt++;}ans+=cnt*f[len-i-1];}return ans;
}int main() {int n;cin>>n;fact(n);string s;cin>>s;cout<<cantor(s)<<endl;return 0;
}/*
in:
10
34152
out:
62
-------
in:
5
bac
out:
3
-------
in:
5
2ac
out:
1
*/
【参考文献】
https://zhuanlan.zhihu.com/p/643917734
https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428?fr=ge_ala
这篇关于康托展开（Cantor Expansion）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
