康托展开

· · 算法·理论

对于 1 到 n 的全排列， 建立排名和排列的双射；

理解：由排列映射到排名可以视为是一种哈希。

原理： 设有 1 到 n 的排列 p_1, p_2, \dots p_n， 其排名应该等于小于该排列的数量 +1

通项公式：\sum_{i = 1}^{n} a_i \times (n - i)!

其中， a_i 是 p_i 右边比 p_i 小的数的个数；

同样的，我们其实可以逆康托展开，其实就是由排名找排列