康托展开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;
    }
}