详解"/>
康托展开详解
康托展开详解 -csdn博客
定义:
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次,因此是可逆的。
原理介绍
**X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0! **
-
A[i] 指的是位于位置i后面的数小于A[i]值的个数,后面乘的就是后面还有多少个数的阶乘
-
说明 :这个算出来的数康拖展开值,是在所有排列次序 - 1的值,因此X+1即为在全排列中的次序
列 :
在(1,2,3,4,5)5个数的排列组合中,计算 34152的康托展开值。
带入上面的公式
- X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0!
=>X = 61
康拖展开代码
//返回数组a中当下顺序的康拖映射
int cantor(int *a,int n)
{int ans=0;for(int i=0;i<n;i++){int x=0;int c=1,m=1;//c记录后面的阶乘for(int j=i+1;j<n;j++){if(a[j]<a[i])x++;m*=c;c++;}ans+=x*m;}return ans;
}
逆康拖展开
- 前面已经说到康拖展开是从序列到自然数的映射且是可逆的,那么逆康拖展开便是从自然数到序列的映射
列 :
在(1,2,3,4,5) 给出61可以算出起排列组合为34152
具体过程如下:
用 61 / 4! = 2余13,说明 ,说明比首位小的数有2个,所以首位为3。
用 13 / 3! = 2余1,说明 ,说明在第二位之后小于第二位的数有2个,所以第二位为4。
用 1 / 2! = 0余1,说明 ,说明在第三位之后没有小于第三位的数,所以第三位为1。
用 1 / 1! = 1余0,说明 ,说明在第二位之后小于第四位的数有1个,所以第四位为5。
逆康拖展开代码
static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘//康托展开逆运算
void decantor(int x, int n)
{vector<int> v; // 存放当前可选数vector<int> a; // 所求排列组合for(int i=1;i<=n;i++)v.push_back(i);for(int i=m;i>=1;i--){int r = x % FAC[i-1];int t = x / FAC[i-1];x = r;sort(v.begin(),v.end());// 从小到大排序a.push_back(v[t]); // 剩余数里第t+1个数为当前位v.erase(v.begin()+t); // 移除选做当前位的数}
}
posted @ 2018-07-11 17:24 i-Curve 阅读( ...) 评论( ...) 编辑 收藏
更多推荐
康托展开详解
发布评论