康托展开学习笔记

发表于 更新于

一种玄学的hash排列的方式

康托展开学习笔记

参考资料

何为康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。 ——百度百科

实际上，康托展开就是给出一个全排列，求它是第几个全排列。

而逆康托展开就是反过来，给出全排列长度和全排列排名，求这个全排列的每一个元素。

实际上，康托展开除了在全排列方面有作用之外，还可以被用来当做一种数列hash，把一整个数列hash成一个值，这样可以大大的节省空间。

如何康托展开

暴力康托展开

我们对于一个全排列，第i位数有n+1-i种选择，如果用变进制数表示，这一位的进制就是n+1-i。

换句话说，如果第i位选择了第k种情况，那么对应的变进制数就是k。

这里我们为了方便，以0为起点做下标。

举个例子，排列:1 4 5 3 2转换成变进制数就是unknown-(02210).

  • 1是排列1 2 3 4 5中的第一项，变进制数为0.
  • 4是排列2 3 4 5中的第三项，变进制数为2.
  • 5是排列2 3 5中的第三项，变进制数为2.
  • 3是排列2 3中的第二项，变进制数为1.
  • 2是排列2中的第一项，变进制数为0.

可以发现，变进制数的第i位的值就是$a_i - \sum_{j=0}^{i-1} [a_j<a_i] +1$.

上面这句话的意思是变进制数的第i位的值就是这个数减去它左边比它小的数再+1.

其实这就是康托展开的定义式。

完整的式子：

$$ans = 1 + \sum_{i=1}^n (\sum_{j=i}^n [a_i < a_j]) \times (n - i)!$$

然后我们暴力做就可以了，用一个used[i]数组来表示第i位是否已经被加入变进制序列，然后把变进制结果转换成十进制就可以了。

代码

这里我们以LuoguP5367 - 【模板】康托展开为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// luogu-judger-enable-o2
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
/* definitions */
const int MAXN = 1e6 + 1;
const int mod = 998244353;
int n,a[MAXN],used[MAXN];
long long ans;
/* functions */
int main(int argc,char *argv[]){
    scanf("%d",&n);
    FOR(i,1,n,1){
        scanf("%d",&a[i]);
        int tmp = a[i];
        FOR(j,1,a[i],1) tmp -= used[j];
        used[a[i]] = 1;
        a[i] = tmp - 1;//暴力计算变进制数
    }
    FOR(i,1,n-1,1) ans = (ans + a[i]) * (n - i) % mod;//转换成十进制
    printf("%lld",ans+1);//最后不要忘了+1
    return 0;
}

树状数组康托展开

我们发现，之前的康托展开是两重循环，时间复杂度$O(n^2)$

当$n \geq 10^4$时，暴力康托展开就承受不起了。

那么我们把used[]数组的求解过程用树状数组来维护前缀和，然后就可以用log的时间求出左侧小于自己的数的个数了。（没用线段树的原因是太难写了）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// luogu-judger-enable-o2
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
/* definitions */
const int MAXN = 1e6 + 1;
const int mod = 998244353;
long long n,a[MAXN],used[MAXN],Tree[MAXN];
long long ans;
/* functions */
inline void Update(int x,int d){
    while(x <= n){
        Tree[x] += d;
        x += lowbit(x);
    }
}
inline long long Query(int x){
    long long ans = 0;
    while(x > 0){
        ans += Tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int main(int argc,char *argv[]){
    used[0] = 1;
    FORL(i,1,MAXN,1) used[i] = (used[i-1] * i) % mod;
    scanf("%lld",&n);
    FOR(i,1,n,1) scanf("%d",&a[i]), Update(i,1);
    ans = 1;
    FOR(i,1,n,1){
        ans = (ans + (used[n - i] * Query(a[i] - 1)) % mod) % mod;
        Update(a[i],-1);
    }
    printf("%lld\n",ans);
    return 0;
}

逆康托展开

我们先把rank--作为第一轮的被除数。

然后从第1位到第n位依次循环,去除以(n-1)!，用商找答案，用余数作为下一轮的被除数。

举个例子，求5项数列中排名第5的全排列：

$5-1=4$

  • 4 / (5 - 1)! = 0 …… 4,所以第一个数是当前未出现的第0个数：1
  • 4 / (4 - 1)! = 0 …… 4,所以第二个数是当前未出现的第0个数：2
  • 4 / (3 - 1)! = 2 …… 0,所以第三个数是当前未出现的第2个数：5
  • 0 / (2 - 1)! = 0 …… 0,所以第四个数是当前未出现的第0个数：4
  • 0 / (1 - 1)! = 0 …… 0,所以第五个数是当前未出现的第0个数：3

所以答案就是：1,2,5,4,3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
/* definitions */
const int MAXN = 1e6 + 1;
long long n,rank,ans[MAXN];
/* functions */
inline long long factor(int t){
    if(t == 0 || t == 1) return 1;
    else return factor(t - 1) * t;
}
inline int recantor(int rank,int len){
    rank--;
    int m = 1,ans = 0;
    bool *book = new bool [len + 1];
    FOR(i,1,len,1) book[i] = true;
    ROF(i,len,2,1){
        int t = factor(i - 1);
        m = rank/t + 1;
        while(book[m] == 0) m++;
        book[m] = 0; ans *= 10; ans += m; num %= t;
    }
    m = 1;
    while(book[m] == 0)m++;
    ans *= 10; ans += m;
    delete [] book;
    return ans;
}
int main(int argc,char *argv[]){
    scanf("%lld%lld",&n,&rank);
    printf("%d",recantor(rank,n));
    return 0;
}

康托展开的应用

康托展开其实可以当做一种变形的hash,它可以把一整个数列映射成一个数，且不会出错。

所以我们在遇到一些题目需要映射数列的时候，就可以利用康托展开来压缩空间。

例题

THE END