如何将0-24中选5的无序无重复组合编码为0-53129的整数？

核心逻辑 #

因为组合是无序的，先把任意组合升序排序，每个唯一组合就对应唯一的有序序列。通过计算该有序序列在所有升序组合里的字典序排名（从0开始计数），就能得到对应的整数编码；反过来，给定整数也能逆推出对应的升序组合。

一、组合转整数（编码） #

假设输入组合排序后为升序序列 (c_0 < c_1 < c_2 < c_3 < c_4)，编码值计算公式为：
code = C(c₀, 1) + C(c₁, 2) + C(c₂, 3) + C(c₃, 4) + C(c₄, 5)
这里的C(n, k)是二项式系数，代表从n个元素中选k个的组合数，若n < k，则C(n, k) = 0。

操作步骤 #

• 把输入的组合按从小到大排序，得到(c_0, c_1, c_2, c_3, c_4)
• 对每个位置i（0到4），计算对应的C(c_i, i+1)
• 将所有计算结果相加，总和就是该组合对应的唯一整数编码

示例 #

拿组合[15,7,12,3,22]举例：

1. 先排序为[3,7,12,15,22]
2. 分别计算：
   • C(3, 1) = 3
   • C(7, 2) = 21
   • C(12, 3) = 220
   • C(15, 4) = 1365
   • C(22, 5) = 26334
3. 求和：3 + 21 + 220 + 1365 + 26334 = 27943，所以该组合的编码是27943

二、整数转组合（解码） #

给定整数code（范围0到53129），逆推对应组合的步骤如下：

操作步骤 #

• 初始化空列表存结果，剩余值r = code，待选元素数量k = 5，起始候选值n = 0
• 当k > 0时循环：
  • 计算C(n, k)，如果这个值大于r，就把n加入结果列表，k减1，n加1
  • 如果这个值小于等于r，就用r减去这个值，n加1
• 最终得到的列表就是升序排列的组合，可按需调整为任意顺序

示例 #

解码code = 27943：

1. 初始状态：r=27943，k=5，n=0
2. 计算C(22,5)=26334 ≤ 27943，r=27943-26334=1609，n=23
3. C(23,5)=33646 > 1609，把22加入结果，k=4，n=23
4. 计算C(15,4)=1365 ≤1609，r=1609-1365=244，n=16
5. C(16,4)=1820>244，把15加入结果，k=3，n=16
6. 计算C(12,3)=220 ≤244，r=244-220=24，n=13
7. C(13,3)=286>24，把12加入结果，k=2，n=13
8. 计算C(7,2)=21 ≤24，r=24-21=3，n=8
9. C(8,2)=28>3，把7加入结果，k=1，n=8
10. 计算C(3,1)=3 ≤3，r=3-3=0，n=4
11. C(4,1)=4>0，把3加入结果，k=0，循环结束
12. 最终得到升序组合[3,7,12,15,22]，对应原组合的任意排列

注意事项 #

• 二项式系数C(n,k)可以用公式C(n,k) = n!/(k!(n-k)!)计算，也可以用递推方式实现，避免大数溢出（如果写代码的话）
• 这套映射完全覆盖所有C(25,5)=53130种组合，每个组合对应唯一整数，每个整数对应唯一组合

内容的提问来源于stack exchange，提问作者Rodolfo