康托展开学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 2.8k | 阅读时长 ≈ 3 分钟

1.什么是康托展开

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

简单来说，康托展开就是对于任意一个全排列，求一个自然数与它对应，即一个全排列到一个自然数的映射，这种映射是唯一的。

2.怎么实现康托展开

公式

$ X=\sum_{i=1}^n a_{i}(i-1)! $

其中，$a_{i}$代表在这个排列中的第$i$个数后面有多少个数比它小。

这个公式求的是当前排列前面有多少个排列

例如，对于排列$14325$，它的康托展开是

$X=0\times(5-1)!+2\times(4-1)!+1\times(3-1)!+0\times(2-1)!+0\times(1-1)!=0+12+2+0+0=14$

所以$14325$前面还有$14$个排列，所以$14325$是第$14+1=15$个排列

本蒟蒻对于这个公式的一些浅显理解:

假设有一个排列$a_{1},a_{2},···,a_{n}$

如果其满足$a_{1} < a_{2}<···< a_{n}$,那么它是第一个排列。所以答案为$1$，计算公式之后不难发现公式正确

如果$a_{2},a_{3},···,a_{n}$中有比$a_{1}$小的数，以这些数为开头的排列必定在$a_{1}$为开头的排列前面，所以要加上这些排列数。确定了开头了之后，其后面还有$(n-1)$个数，可以构成$(n-1)!$种序列，所以公式第一项为比$a_{1}$小的数的个数乘以$(n-1)!$

以此类推，可以得到该序列的排位。

代码实现

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
#include<bits/stdc++.h>
using namespace std;

const int N = 110;

long long sum[N];
int a[N] , n , Min[N];

void fc(int n)//预处理阶乘
{
	sum[0] = 1;
	for(int i = 1; i <= n - 1; i ++)
	  sum[i] = i * sum[i - 1];
}

void get(int pos)//预处理ai
{
	for(int i = pos + 1; i <= n; i ++)
	  if(a[i] < a[pos]) Min[pos] ++;
}

long long cantor()//康托展开
{
	long long ans = 0; 
	for(int i = 1; i <= n; i ++)
	  ans += Min[i] * sum[n - i];
	return ans; 
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
   fc(n);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++) get(i);
	printf("%lld" , cantor() + 1);
	return 0;
}

3.逆康托展开

知道了如何给定排列求序号，因为排列与序号一一对应，所以自然可以用序号求排列。

逆康托展开其实就是把康托展开反向计算。

假设字典序号为$pos$，共有$n$个数

首先用$pos\div(n-1)!$，余数自然就是$\sum_{i=2}^n a_{i}(n-i)! $,商就是 $a_{1}$

如此反复，可求得$a_{1},a_{2},···,a_{n}$

例如：给定$pos=15,n=5$，所以有$pos-1=14$个比它小的序列

$14\div(5-1)!=0······14,a_{1}=0$

$14\div(4-1)!=2······2,a_{2}=2$

$2\div(3-1)!=1······0,a_{3}=1$

$0\div(2-1)!=0······0,a_{4}=0$

$0\div(1-1)!=0,a_{5}=0$

接下来，在$1,2,3,4,5$中，有$0$个比它小的数的数是$1$，所以第一位为$1$

在$2,3,4,5$中，有$2$个比它小的数的数是$4$，所以第二位为$4$

在$2,3,5$中，有$1$个比它小的数的数是$3$，所以第三位为$3$

在$2,5$中，有$0$个比它小的数的数是$2$,所以第四位为$2$

第五位为$5$

综上，原序列为$14325$

代码实现

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
#include<bits/stdc++.h>
using namespace std;

const int N = 110;

long long sum[N];
int a[N] , n , pos , Min[N];
bool use[N];

void fc(int n)
{
	sum[0] = 1;
	for(int i = 1; i <= n - 1; i ++)
	  sum[i] = i * sum[i - 1];
}

void recantor(int pos)
{
	for(int i = n - 1; i >= 0; i --)
	{
		int s = 0;
		Min[n - i] = pos / sum[i] , pos = pos % sum[i];
		for(int j = 1; j <= n; j ++)
		{
			if(! use[j])
			  s ++;
			if(s == Min[n - i] + 1)
			 {
			 	a[n - i] = j;
			 	use[j] = 1;
			 	break;
			}  
		}
	}
	  
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> pos;
    fc(n);
	recantor(pos - 1);
	for(int i = 1; i <= n; i ++)
	  cout << a[i];
	return 0;
}

4.例题

P3014[USACO11FEB]牛线Cow Line

P5367【模板】康托展开