河北大学暑期程序设计训练每日知识分享-day21

每日分享——康托展开&逆康托展开

定义

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。

设有n个数（1,2,3,4,…,n）,组成不同 n! 种的排列组合，其康托展开唯一且最大约为n!
康托展开表示的就是当前排列在n个不同元素的全排列中的名次。
时间复杂度O(n^2^)

适用范围

搜索，动态规划中常常用一个数字来表示一种状态，大大降低空间复杂度

公式

X=a1×(n?1)!+a2×(n?2)!+?+an×0!
X代表当前排列在全排列中的排名，ai 代表当前数是数列中未出现的数中第几小的 从0开始计数，0是第一小的数

例如 4,2,3,14,2,3,1

4 是当前数列中未出现的数中第3 小的，X+=3?(4?1)!

2 是当前数列中未出现的数中第1 小的，X+=1?(4?2)!

3 是当前数列中未出现的数中第1 小的，X+=1?(4?3)!,因为22 已经输出过了，所以不算

1 是当前数列中未出现的数中第0 小的，X+=0?(4?4)!
这要就求出了4,2,3,14,2,3,1 所唯一对应的在全排列中的名次X=22

注意到我们每次要用到 当前有多少个小于它的数还没有出现
这里用树状数组统计比它小的数出现过的次数就可以了，可以优化到O(nlogn)

代码

向预处理阶乘

1
2
3
4
5
6
7
void init() {
    fact[0] = 1;
    for(int i = 1;i <= 9; ++i) fact[i] = fact[i - 1] * i;
    // 递推求阶乘
}
// 或者直接打表
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

cantor函数

1
2
3
4
5
6
7
8
9
10
11
12
int cantor(int a[],int n) {
    int res = 0;
    for(int i = 0;i < n; ++i) {
        int cnt = 0;
        for(int j = i + 1;j < n; ++j) if(a[j] < a[i]) cnt ++;
        // 找到a[i]是当前数列中未出现的数中第几小的
        // 从1开始，即1-n的全排列
        // 从0开始，就变成了0-n的全排列，记得变通
        res += cnt * fact[n - i - 1];// 累加值
    }
    return res + 1;// 如果输出的是排名就要 + 1，如果是hash值可以直接返回 res
}

逆康托展开

因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。

首先把排名XX 减去11 ，变成以00 开始的排名

例如求 1,2,3,41,2,3,4 的全排列序列中，排名第2222 的序列是什么

22?1=21 ， 21 代表着有多少个排列比这个排列小

  • 第一个数 a[1]
    ?21/(4?1)!?=3 比a[1] 小且没有出现过的数有3 个，a[1]=4a[1]=4
    X = X mod 3×(4?1)! = 3
  • 第二个数a[2]
    ?3/(4?2)!?=1 比a[2] 小且没有出现过的数有1 个，所以a[2]=2a[2]=2
    X = X mod 1 × (4?2)! = 1
  • 第三个数a[3]
    ?1/(4?3)!?=1 比a[3] 小且没有出现过的数有1 个，所以a[3]=3a[3]=3
    X = X mod 1×(4?3)! = 0
  • 第四个数a[4]
    ?0/(4?4)!?=0 比a[4] 小且没有出现过的数有0 个，所以a[4]=1a[4]=1
    最终得到数列4,2,3,1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> incantor(int x,int n) {
    x--;// 得到以0开始的排名
    vector<int> res(n);// 保存数列答案
    int cnt;
    bool st[10];// 标记数组
    memset(st,0,sizeof st);
    for(int i = 0;i < n; ++i) {
        cnt = x/fact[n - i - 1];// 比a[i]小且没有出现过的数的个数
        x %= fact[n - i - 1];// 更新 x
        for(int j = 1;j <= n; ++j) {// 找到a[i]，从1开始向后找
            if(st[j]) continue;// 如果被标记过，就跳过
            if(!cnt) {// 如果cnt == 0说明当前数是a[i]
                st[j] = 1;//标记
                res[i] = j;// 第i位是j
                break;
            }
            cnt --;// 如果当前不是0，就继续往后找
        }
    }
    return res;// 返回答案
}