康托展开c++实现
目录
介绍
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
代码实现
/**
* 康托展开
* num[]: 全排列序列(下标从1开始)
* LEN :全排列长度
**/
int cantor(int num[], LEN){
int ans = 0,sum = 0;
for(int i = 1;i < LEN;i++){
for(int j = i + 1;j <= LEN;j++)
if(num[j] < num[i])
sum++;
// factorial:阶乘
ans += sum * factorial[LEN - i];
sum = 0;
}
return ans + 1;
}
/**
* 康托逆展开
* index: 全排列索引
* LEN :全排列长度
**/
void decantor(int index, int LEN){
int num[LEN + 1];
set<int>mySet = {1,2,3,4,5,6,7,8,9};
int div, mod, j;
set<int>::iterator it;
for(int i = 1;i <= LEN;i++){
div = index / factorial[LEN - i];
mod = index % factorial[LEN - i];
for(j = 0,it = mySet.begin();j < div;j++)it++;
num[i] = *it;
mySet.erase(it);
index = mod;
}
}
历史评论
开始评论