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

十月 17, 2019 938

简介

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

——Wikipedia

公式

直接给式子吧

对于一个长度为 n 的排列，它在全排列中的排名为
MATHJAX-SSR-613
其中 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之后再转化回排列，进而得到结果