📐 四阶康托展开
简介
康托展开（Cantor Expansion）是一种将排列映射到自然数的双射方法。四阶康托展开特指对 4 个元素的排列进行编码。
数学原理
康托展开公式：X = a[n-1]×(n-1)! + a[n-2]×(n-2)! + ... + a[1]×1! + a[0]×0!
其中 a[i] 表示在第 i 个位置之后，有多少个比第 i 个位置小的数字。
四阶示例
对于排列 [3, 1, 4, 2]：
- 第 1 位 3：后面有 2 个比 3 小的数 (1,2) → a[3]=2
- 第 2 位 1：后面有 0 个比 1 小的数 → a[2]=0
- 第 3 位 4：后面有 1 个比 4 小的数 (2) → a[1]=1
- 第 4 位 2：后面有 0 个数 → a[0]=0
康托展开值 = 2×3! + 0×2! + 1×1! + 0×0! = 12 + 0 + 1 + 0 = 13
4! = 24 种排列
1234→0 1243→1 1324→2 1342→3
1423→4 1432→5 2134→6 2143→7
2314→8 2341→9 2413→10 2431→11
3124→12 3142→13 3214→14 3241→15
3412→16 3421→17 4123→18 4132→19
4213→20 4231→21 4312→22 4321→23
应用场景