【算法笔记】康托展开


介绍

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

公式

\(X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_1\cdot0!\)
其中, \(a_{i}\) 为整数,并且 \(0\leq a_{i}<i,1\leq i\leq n\)
\(a_{i}\) 的意义参见举例中的解释部分

解释

因为排列是按字典序排名的,因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同,那么如果这一位如果不相同,就按这一位排序。

举例

例如,\(3~5~7~4~1~2~9~6~8\) 展开为 \(98884\)。因为\(X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884\).

解释:

排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!

排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!

以此类推,直至0*0!

用途

显然,\(n\)\((0 \sim n-1)\)全排列后,其康托展开唯一且最大约为\(n!\),因此可以由更小的空间来储存这些排列。由公式可将\(X\)逆推出唯一的一个排列。

康托展开的逆运算

既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出n的全排列中第x大排列。

\(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\). 所以这个数是 \(45321\).

按以上方法可以得出通用的算法。

优化

树状数组

我们在处理 \(a_i\) 时,要每次统计小于当前一位数且没有被选过的数字个数,复杂度为 \(\Theta (n^2)\) .
考虑使用树状数组,建树时均赋值为 \(1\) ,被选中后 \(add(1, n, -1)\) 即可。
时间复杂度为 \(\Theta (n \log n)\)


文章作者: sfc9982
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
  目录