笔记 - Cantor 展开与逆 Cantor 展开

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

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}^nD_i(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)\) 的算法

我们有如下定理

定理 - 1

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

证明

由乘法原理立得

\(\Box\)

自然的,我们有推论

推论 - 1

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

证明

\[ d(A)=\sum_{i=1}^n|D_i(A)|+1=\sum_{i=1}^n p_i(n-i)!+1 \]

\(\Box\)

设求 \(P_A\) 的时间复杂度为 \(O(P(n))\), 则该算法的时间复杂度是 \(O(P(n)+n)\), 所以算法复杂度的瓶颈就在于如何快速求 \(P_A\)

显然暴力做法的复杂度是 \(O(n^2)\), 我们也可以使用树状数组将其优化到 \(O(n\log n)\)

所以该算法的复杂度即为 \(O(n\log n)\)

Show code

逆 Cantor 展开

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

首先我们有定理

定理 - 2

\[ \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} \]

\(\Box\)

也就是说,\(n!=\sum_{i=1}^n(n-i)\cdot (n-i)!\geqslant\sum_{i=1}^np_i(n-i)!\)

此式说明,对于给定的 \(d(A)\),

\[ p_i=\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)\)

Show code

例题


参考资料