「康托展开」学习笔记
2022/2/6 23:20:53
本文主要是介绍「康托展开」学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
至于笔者为什么写这篇学习笔记,其实也没有什么 特殊原因(CantorSort2919
前置芝士:
相信大家都学过 排列组合,我们记 $P_n^n$ 或 $A_n^n$ 为 $1\sim n$ 的 全排列;
并且,全排列还可以按照 字典序 进行排序,
举个栗子,
$A=\{1,2,3,4\}$
$B=\{1,2,3,4,5\}$
其中 $len_a<len_b$,所以 $A$ 的字典序 小于 $B$。
而 康托展开(Cantor Expansion,CE),记录的就是 $1\sim n$ 全排列的 排名。
正题:
康托展开
让笔者再举一个栗子:
$A=\{2,5,3,4,1\}$。
我们知道长为 $5$ 的排列 $\{2,5,3,4,1\}$ 大于以 $1$ 为第一位的 任何排列,以 $1$ 为第一位的排列有 $4!$ 种。
非常好理解。
但是我们对第二位的 $5$ 而言,它大于 第一位与这个排列相同的,而这一位比 小的 所有排列。不过我们要注意的是,这一位不仅要比 $5$ 小,还要满足没有在当前排列的前面出现过,不然统计就重复了。因此这一位为 $1,3,4$,第一位为 $2$ 的所有排列都比它要小,数量为 $3\times 3!$。
按照这样统计下去,答案就是 $1+4!+3\times 3!+2!+1=46$。
注意,
我们统计的是排名,因此最前面要 $+1$。
注意到我们每次要用到 当前有多少个小于它的数还没有出现,这里可以用 树状数组 统计 比它小的数出现过的次数。
逆康托展开
因为排列的排名和排列是 一一对应 的,所以康托展开满足 双射关系,是 可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名,就可以推出这个排列。因为 $4!$
是严格大于 $3\times 3!+2\times 2!+1\times 1!$ 的,所以可以认为对于长度为 $5$ 的排列,排名 $x$ 除以 $4!$ 向下取整就是有多少个数小于这个排列的第一位。
用式子来表达,就是第一位记作 $y$ 时,有:
$$y=\lfloor \frac{x}{4!}\rfloor$$
推广,即可得出,$1\sim n$ 的全排列中,第 $x$ 名的排列的第一位 $y$ 的计算式子:
$$y=\lfloor \frac{x}{(n-1)!}\rfloor$$
这篇关于「康托展开」学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?