康托展开与逆康托展开

115 阅读 0 评论 76 点赞

我是靠谱客的博主细心仙人掌，这篇文章主要介绍康托展开与逆康托展开，现在分享给大家，希望可以做个参考。

1.康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合
例如对于 1 ~ 4 的一个全排列， [1, 2, 3, 4] 和 [4, 3, 2, 1]分别为第一个和最后一个排列。
康托展开公式为：
*X=a[n](n-1)!+a[n-1](n-2)!+…+a[i]*(i-1)!+…+a[1]0!
a[i] 指的是位于位置i后面的数小于a[i]值的个数,后面乘的就是后面还有多少个数的阶乘

复制代码

1
2
3
4
5
6
7
8
9
10
11
int contor(int len, int* a) {		// len为数组长度， 
    int num = 0;
     for (int i = 0; i < len; ++i) {
        int cnt = 0; // 在 i 之后，比 i 还小的有几个
        for (int j = i + 1; j < len; ++j)
            if (a[i] > a[j]) ++cnt;
        num += cnt * fact[len - i - 1];
    }
    return num + 1;	
}

2. 逆康托展开
康托展开是从序列到自然数的映射且是可逆的，逆康托展开便是从自然数到序列的映射

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
vector<int> revContor(int bits, int num) {
    num = num - 1;	
    vector<bool> vis(bits + 1, false);
    vector<int> permutation(bits, -1);
    
    int n, residue = num;
    for (int i = 0; i < bits; i++) {
        n = residue / (fact[bits - i - 1]);
        residue %= (fact[bits - i - 1]);
        for (int j = 1; j <= bits; j++) {
            if (!vis[j] && !(n--)) {
                vis[j] = true;
                permutation[i] = j;
                break;
            }
        }
    }
    return permutation;  //输出对应的全排列
}