介绍
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
公式
\(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)\)