算法笔记 | 康托展开及其逆运算
康托展开
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩.
而对于一个序列,其所有排列按照字典序排序的顺序从小到大编号, 康拓展开就是用于计算这种排列在其顺序中的位置.
举个栗子╰(°▽°)╯
对于序列{1,3,2}, 它的顺序位于其所有排列的第2位, 前一位为{1,2,3}.
其公式如下:
其中 T 为其排列的顺序, A_i 为序列中第 i 个元素, n 为序列总长度.
我们可以看到, 其中需要计算n!, 这一步可以通过打表来优化时间复杂度, 而当n!过大的时候, 就需要大整数计算了.
康托展开的逆运算
因为康托展开是一个双射, 那么一个合法的 T 值必定对应一个唯一的序列, 也就是说可以反向计算顺序为 T 的序列.
1.输入n, T
2.计算第i位对应的值(i从1开始):
a)将T-1,意为前面有T-1个排列
b)currI = T/(n-i)!, currI即为当前位数
c)如果currI已经被使用过,那么currI++
d)currM = T%(n-i)!, currM为剩下的数
e)T = currM
3.输出所有的currI
那么直接来道题叭:CodeVS 2972 - 选课
但是这道题...数据并不是很强...只有三个监测点
资料参考 Joseph Galante:Generalized Cantor Expansions