「初赛」康托展开学习笔记

简介

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

——Wikipedia

公式

直接给式子吧

对于一个长度为 $n$ 的排列,它在全排列中的排名为

其中$a_i$为给定排列前 $i - 1$个数中 小于 $a_i$ 的 没有出现的 数的数量

例子:

1
2
3
4
5
t = {1, 6, 4, 5, 3, 2}
那么
a = {0, 4<2,3,4,5>, 2<2,3>, 2<2,3>, 1<2>, 0}
其中<>里具体说明了是哪几个数
此时 x = 114

另外,$x-1$就是有多少个排列比给定排列要小。这个很显然。

逆康托展开

前面说了是可逆的,那么说一说怎么逆回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
如n=5,x=96时:

首先用96-1得到95,说明x之前有95个排列.(将此数本身减去1)
用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4.
用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5.
用5去除2!得到2余1,类似地,这一位是3.
用1去除1!得到1余0,这一位是2.
最后一位只能是1.
所以这个排列是{4, 5, 3, 2, 1}.

再给一个例子:
n = 6, x = 123
123 / (5!) = 1...3
3 / (4!) = 0...3
...(结果都是0...3)
3 / (2!) = 1...1
1 / (1!) = 1...0
0 / (0!) = 0...0

所以最终排列为{2, 1, 3, 5, 6, 4}

用途

写这玩意有什么用?打开NOIP2018提高组初赛第21题看程序写输出,他要求的就是给定排列往后数t个得到的排列

使用这个方法就可以将给定排列转化为排名,加t之后再转化回排列,进而得到结果