32位空间下64种无重复0-7项组合的整数映射方案咨询

可行性验证 #

首先计算所有可能的组合总数：
C(64,0) + C(64,1) + C(64,2) + C(64,3) + C(64,4) + C(64,5) + C(64,6) + C(64,7) = 360,615,213
而32位无符号整数的最大值是4,294,967,296，远大于组合总数，因此完全可以实现映射。

方案一：分字段编码（直观易实现） #

将32位整数分为两部分：

• 低3位：存储组合的物品数量k（0-7，正好用3位表示）
• 高29位：存储该组合在对应k元组合集合中的字典序索引（从0开始）

编码步骤

1. 给64种物品分配唯一编号0~63。
2. 对目标组合：
   • 若为空组合（k=0），直接输出整数0。
   • 若为k元组合（1≤k≤7）：
     a. 将组合内的物品编号按升序排序，得到序列a₀ < a₁ < ... < aₖ₋₁。
     b. 计算该序列在所有k元组合中的字典序索引，公式为：
     index = C(a₀,1) + C(a₁,2) + ... + C(aₖ₋₁,k)
     （注：C(n,r)为组合数，当n<r时结果为0）
     c. 将index左移3位，与k进行按位或操作，得到最终32位整数：(index << 3) | k。

解码步骤

1. 从32位整数中提取低3位得到k，高29位右移3位得到index。
2. 若k=0，对应空组合。
3. 若1≤k≤7，根据index反向推导物品序列：
   • 初始化prev = -1，剩余索引remaining = index。
   • 依次求解每个a_i：
     对于第i个位置（从1到k），找到最小的x满足C(x,i) > remaining，则a_{i-1} = x-1，然后更新remaining = remaining - C(x-1,i)。
   • 最终得到的a₀~aₖ₋₁即为组合的物品编号。

方案二：全局唯一索引编码 #

将所有组合按“空组合→1元组合→2元组合→…→7元组合”的顺序排列，每个组合对应一个全局唯一的32位整数索引。

编码步骤

1. 给64种物品分配唯一编号0~63。
2. 对目标组合：
   • 若为空组合，输出0。
   • 若为k元组合：
     a. 按升序排序得到a₀ < a₁ < ... < aₖ₋₁。
     b. 计算前缀组合数总和：prefix = C(64,0) + C(64,1) + ... + C(64,k-1)。
     c. 计算k元组合内的索引（同方案一的index）。
     d. 最终整数为prefix + index。

解码步骤

1. 给定整数N，找到最大的k使得sum_{m=0}^{k-1} C(64,m) ≤ N。
2. 计算index = N - sum_{m=0}^{k-1} C(64,m)。
3. 后续步骤同方案一的解码，通过index推导物品序列。

组合数计算说明 #

组合数C(n,r)可通过递推公式计算：
C(n,0) = 1
C(n,r) = C(n-1,r-1) + C(n-1,r)
或直接用公式：C(n,r) = n!/(r!*(n-r)!)，但需注意计算时避免溢出（可使用64位整数临时存储中间结果，再转32位）。

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