康托展开与逆康托展开

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 字数： 1.8k

康托展开与逆康托展开

1 康托展开

1.1 定义

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

之所以说是空间压缩,是因为当我们进行哈希运算时，如果是一个正常的长度为$n$数列，数的范围在$1 \to n$ 的情况下，这个数列总共存在的情况有$n^n$种，我们将数列映射为整数时，则至少需要$n^n$这个数量级以上的空间

而$n$的全排列很明显只有$n!$种情况，也就是说，会没有必要的浪费很多空间，如何将空间降低呢，我们就需要用到康托展开与逆康托展开

举个例子，当$n == 9$时，普通哈希算法需要的空间为$9 ^ 9 = 387420489$，而康托展开只需要$9! = 3682880$的空间即可

康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

1.2 康托展开运算

其中$a_i$为$0 \le a_i < i$的非负整数，$1 \le i \le n$

$a_i$ 表示原数的第$i$位在当前未出现的元素中是排在第几个（也可以理解为位置$i$后面的数有多少个是小于第$i$位的数）

1.3 举个例子

在$(1, 2, 3, 4)$的全排列中，我们计算排列 $(2, 4, 1, 3)$是第几小的排列

此时我们可以发现 2 后面只有一个比它小的数

所以$a_4 = 1$，同理$a_3 = 2, a_2 = 0, a_1 = 0$

代入公式则可以计算出此时

所以有10个排列比该排列小，该排列的次序应为11

1.4 实现技巧

统计当前未出现的元素的排的名次时，我们可以采用不同的方式

当$n$很小是，我们可以按顺序暴力遍历所有元素，查看是否出现，统计其名次

当$n$比较大时，我们可以考虑通过线段树来查询

2 逆康托展开

既然康托展开是一个全排列到一个自然数的双射，那么我们一定可以通过它的名次，来确定它的具体排列情况。

假设我们想知道$5$的全排列中的第$34$小的排列

我们知道，有$33$个排列小于它。我们便可以通过上述运算过程的逆过程推出该排列的具体内容

因此$a_5 = 1$即未出现的数字中有一个小于它，即它是$2$

因此$a_4 = 1$即未出现的数字中有一个小于它，即它是$3$

因此$a_3 = 2$即未出现的数字中有两个小于它，即它是$5$

因此$a_2 = 0$即未出现的数字中有零个小于它，即它是$1$

最后一位显然是 $4$

因此该排列为 $(2, 3, 5, 1, 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
int a[12], fac[12];
bool vis[12];
void getfac(int n){
    fac[0] = 1;
    for(int i = 1; i < n; ++i) fac[i] = fac[i - 1]*i;
}
int cantor(int n){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        int cnt = 0;
        for(int j = i + 1; j < n; ++j) if(a[i] > a[j]) ++cnt;
        ret += cnt*fac[n - 1 - i];
    }
    return ret;
}
void decantor(int x, int n){
    for(int i = 1; i <= n; ++i) vis[i] = false;
    int tot = 0;
    for(int i = n; i >= 1; --i){
        int q = x/fac[i - 1];
        int cnt = 0;
        for(int j = 1; j <= n; ++j){
            if(vis[j]) continue;
            if(++cnt > q){
                a[tot++] = j;
                vis[j] = true;
                break;
            }
        }
        x = x%fac[i - 1];
    }
}

4 应用价值

4.1 快速确定某排列的名次

4.2 知道名次快速确定排列的内容

4.3 压缩哈希空间减低空间复杂度

5 经典例题（八数码）

其中经典例题

hdu1043 Eight 八数码

给定一个现有的九宫格布局，请输出将它移动至初始状态的移动方法的步骤

便是利用康托展开加bfs解决的

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/* ***********************************************
Author        :linxi
Created Time  :2019年02月09日 星期六 10时58分59秒
File Name     :1.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 4e5 + 5;
//head
int pre[maxn];
char dir[maxn];
int tox[] = {0, 0, 1, -1};
int toy[] = {1, -1, 0, 0};
char cdir[] = {'l', 'r', 'u', 'd'};

int a[12], fac[12];
bool vis[12];
void getfac(int n){
    fac[0] = 1;
    for(int i = 1; i < n; ++i) fac[i] = fac[i - 1]*i;
}
int cantor(int n){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        int cnt = 0;
        for(int j = i + 1; j < n; ++j) if(a[i] > a[j]) ++cnt;
        ret += cnt*fac[n - 1 - i];
    }
    return ret;
}
void decantor(int x, int n){
    for(int i = 1; i <= n; ++i) vis[i] = false;
    int tot = 0;
    for(int i = n; i >= 1; --i){
        int q = x/fac[i - 1];
        int cnt = 0;
        for(int j = 1; j <= n; ++j){
            if(vis[j]) continue;
            if(++cnt > q){
                a[tot++] = j;
                vis[j] = true;
                break;
            }
        }
        x = x%fac[i - 1];
    }
}

bool judge(int x, int y){
    if(x < 0 || x >= 3) return false;
    if(y < 0 || y >= 3) return false;
    return true;
}
void bfs(){
    rep(i, 0, 9) a[i] = i + 1;
    int s = cantor(9);
    queue<int> qs;
    qs.push(s);
    pre[s] = 0;
    while(!qs.empty()){
        s = qs.front(), qs.pop();
//        pd(s);
        decantor(s, 9);
        int x = -1, y = -1;
        rep(i, 0, 9){
            if(a[i] != 9) continue;
            x = i/3, y = i%3;
            break;
        }
        rep(i, 0, 4){
            int xx = x + tox[i], yy = y + toy[i];
            if(!judge(xx, yy)) continue;
            swap(a[x*3 + y], a[xx*3 + yy]);
            int ss = cantor(9);
            if(pre[ss] == -1){
                qs.push(ss);
                pre[ss] = s;
                dir[ss] = cdir[i];
            }
            swap(a[x*3 + y], a[xx*3 + yy]);
        }
    }
}

char s[maxn];

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    mm(pre, -1);
    getfac(9);
    bfs();
    while(ss(s) != EOF){
        if(s[0] == 'x') s[0] = '9';
        a[0] = s[0] - '0';
        rep(i, 1, 9){
            ss(s);
            if(s[0] == 'x') s[0] = '9';
            a[i] = s[0] - '0';
        }
        int s = cantor(9);
        if(pre[s] == -1){
            puts("unsolvable");
            continue;
        }
        while(s != 0){
            printf("%c", dir[s]);
            s = pre[s];
        }
        puts("");
    }
    return 0;
}
/*


*/