康托展开

康托展开可以用来求一个 $1\sim n$ 的任意排列的排名。

什么是排列的排名？

把 $1\sim n$ 的所有排列按字典序排序，这个排列的位次就是它的排名。

时间复杂度？

康托展开可以在的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到 $O(n\log n)$ 。

怎么实现？

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

比如的排列，，因为在第位出现不同，则的排名在前面。

举个栗子

我们知道长为的排列大于以为第一位的任何排列，以为第一位的的排列有种。这是非常好理解的。但是我们对第二位的而言，它大于 第一位与这个排列相同的，而这一位比小的 所有排列。不过我们要注意的是，这一位不仅要比小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为或，第一位为的所有排列都比它要小，数量为 $3\times 3!$ 。

按照这样统计下去，答案就是 $1+4!+3\times 3!+2!+1=46$ 。注意我们统计的是排名，因此最前面要。

注意到我们每次要用到 当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就可以了。

逆康托展开

因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。

如果我们知道一个排列的排名，就可以推出这个排列。因为是严格大于 $3\times 3!+2\times 2!+1\times 1!$ 的，所以可以认为对于长度为的排列，排名除以向下取整就是有多少个数小于这个排列的第一位。

引用上面展开的例子

首先让，代表着有多少个排列比这个排列小。 $\lfloor\frac {45}{4!}\rfloor=1$ ，有一个数小于它，所以第一位是。

此时让排名减去 $1\times 4!$ 得到， $\lfloor\frac {21}{3!}\rfloor=3$ ，有个数小于它，去掉已经存在的，这一位是。

$21-3\times 3!=3$ ， $\lfloor\frac {3}{2!}\rfloor=1$ ，有一个数小于它，那么这一位就是。

让 $3-1\times 2!=1$ ，有一个数小于它，这一位是剩下来的第二位，，剩下一位就是。即。

实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第个没有被选上的数，这里也可以用线段树维护，时间复杂度为 $O(n\log n)$ 。

本页面最近更新：2021/8/6 23:58:35，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, Great-designer, hjsjhn, Ir1d, MegaOwIer, wjy-yy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用