版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 笔记 - Cantor展开与逆Cantor展开 categories:
洛谷给我推了个模板题, 就顺便补一下笔记
Cantor 展开是用于求排列字典序的算法, 逆 Cantor 展开即根据字典序还原排列的算法
{% note warning %} https://cplib.tifa-233.com/src/code/edh/cantor.hpp, https://cplib.tifa-233.com/src/code/edh/cantor_inv.hpp 存放了笔者对该算法/数据结构的最新实现, 建议前往此处查看相关代码 {% endnote %}
<!-- more -->$\mathbb{Z}_a^b:=[a,b]\cap\mathbb{Z}$
在不引起歧义的情况下, 可将 $\mathbb{Z}_a^b$ 简记为 $a..b$
$f_n:=\left((n-1)!,(n-2)!,...,1!,0!\right)\in\mathbb{N}^n$
$1..n$ 的排列: 称 $A:=(a_1,a_2,\dots,a_n)\in(\mathbb{Z}_1^n)^n$ 为 $1..n$ 的排列, 若
$$ {a_1,a_2,\dots,a_n}={1,2,...,n} $$
为了方便下文叙述, 我们定义
$1..n$ 的所有排列组成的集合为 $S_n$
显然 $|S_n|=n!$
对 $1..n$ 的排列 $A=(a_1,a_2,\dots,a_n)$,
$$ D_i(A):={(d_1,d_2,...,d_n)\in S_n~|~d_i<a_i;~\forall j\in \mathbb{Z}_1^{i-1}, d_j=a_j} $$
在不引起歧义的情况下, 可将 $D_i(A)$ 简记为 $D_i$
$1..n$ 排列的字典序: 对 $1..n$ 的排列 $A=(a_1,a_2,\dots,a_n)$, 定义其序号为
$$ d(A)=\left|\bigcup_{i=1}^nDi(A)\right|+1=\sum{i=1}^n|D_i(A)|+1 $$
显然
对 $1..n$ 的排列 $A=(a_1,a_2,\dots,a_n)$, 定义 $P_A:=(p_1,p_2,\dots,p_n)$, 其中 $p_i=|{a_j:a_j<a_i,\forall j\in\mathbb{Z}_i^n}|,~i=1,2,...,n$
如 $P_{(3,2,1,4)}=(2,1,0,0)$
显然 $p_i\leqslant n-i$
Cantor 展开即对 $1..n$ 的排列 $A$ 求 $d(A)$ 的算法
我们有如下定理
对任意 $1..n$ 的排列 $A$, $|D_i(A)|=p_i(n-i)!$
由乘法原理立得
<a href="#p-t-1" id="end-t-1">$\Box$</a>
自然的, 我们有推论
对任意 $1..n$ 的排列 $A$, $d(A)=P_Afn^T+1=\sum{i=1}^n p_i(n-i)!+1$
$$ d(A)=\sum_{i=1}^n|Di(A)|+1=\sum{i=1}^n p_i(n-i)!+1 $$
<a href="#p-ifr-1" id="end-ifr-1">$\Box$</a>
设求 $P_A$ 的时间复杂度为 $O(P(n))$, 则该算法的时间复杂度是 $O(P(n)+n)$, 所以算法复杂度的瓶颈就在于如何快速求 $P_A$
显然暴力做法的复杂度是 $O(n^2)$, 我们也可以使用树状数组将其优化到 $O(n\log n)$
所以该算法的复杂度即为 $O(n\log n)$
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp cantor-exp/Cantor_expansion.hpp %} </details>逆 Cantor 展开即对 $1..n$ 的排列 $A$, 已知 $d(A)$ 求 $A$ 的算法
首先我们有定理
$$ \forall n\in\mathbb{N}^+,~n!=\sum_{i=0}^{n-1}i\cdot i! $$
$$ \begin{aligned} n!&=(n-1+1)\cdot(n-1)!\ &=(n-1)\cdot(n-1)!+(n-1)!\ &=(n-1)\cdot(n-1)!+(n-2)!\cdot(n-2)!+(n-3)!\ &...\ &=\sum_{i=0}^{n-1}i\cdot i! \end{aligned} $$
<a href="#p-t-2" id="end-t-2">$\Box$</a>
也就是说, $n!=\sum{i=1}^n(n-i)\cdot (n-i)!\geqslant\sum{i=1}^np_i(n-i)!$
此式说明, 对于给定的 $d(A)$,
$$ pi=\left\lfloor{d(A)-\sum{j=1}^{i-1}p_j(n-j)!-1\over (n-i)!}\right\rfloor $$
显然 $P_A$ 可以 $O(n)$ 求得
设根据 $P_A$ 求 $A$ 的时间复杂度为 $O(P'(n))$, 则该算法的时间复杂度为 $O(P'(n)+n)$, 所以算法复杂度的瓶颈就在于如何快速根据 $P_A$ 求 $A$
显然暴力做法的复杂度是 $O(n^2)$, 我们也可以使用平衡树等将其优化到 $O(n\log n)$
所以该算法的复杂度即为 $O(n\log n)$
<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp cantor-exp/inverse_Cantor_expansion.hpp %} </details>