仓库源文，站点原文

title: 笔记 - Cantor展开与逆Cantor展开 categories:

笔记
算法竞赛 tags:
算法竞赛
笔记
模板
数学
组合数学
Cantor展开
逆Cantor展开
树状数组
平衡树 date: 2020-11-14 00:12:11

洛谷给我推了个模板题, 就顺便补一下笔记

Cantor 展开是用于求排列字典序的算法, 逆 Cantor 展开即根据字典序还原排列的算法

一些定义

$\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 $$

显然
- $d(1,2,...,n)=1$
- $d(n,n-1,...,1)=n!$
对 $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 展开

Cantor 展开即对 $1..n$ 的排列 $A$ 求 $d(A)$ 的算法

我们有如下定理

<a href="#end-t-1" id="t-1">定理 - 1</a>

对任意 $1..n$ 的排列 $A$, $|D_i(A)|=p_i(n-i)!$

<a href="#t-1" id="p-t-1">证明</a>

由乘法原理立得

自然的, 我们有推论

<a href="#end-ifr-1" id="ifr-1">推论 - 1</a>

对任意 $1..n$ 的排列 $A$, $d(A)=P_Afn^T+1=\sum{i=1}^n p_i(n-i)!+1$

<a href="#ifr-1" id="p-ifr-1">证明</a>

$$ d(A)=\sum_{i=1}^n|Di(A)|+1=\sum{i=1}^n p_i(n-i)!+1 $$

设求 $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 展开

逆 Cantor 展开即对 $1..n$ 的排列 $A$, 已知 $d(A)$ 求 $A$ 的算法

首先我们有定理

<a href="#end-t-2" id="t-2">定理 - 2</a>

$$ \forall n\in\mathbb{N}^+,~n!=\sum_{i=0}^{n-1}i\cdot i! $$

<a href="#t-2" id="p-t-2">证明</a>

$$ \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} $$

也就是说, $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)$