Colex 与 Mixed-radix：给多轮选择编号

从一次选择说起

记

[𝑁] ≔ {0, 1, \dots, 𝑁 - 1} .

从 $[𝑁]$ 中选择 $𝑚$ 个元素时，如果只关心选中了哪些元素，而不关心选取顺序，那么结果就是 $[𝑁]$ 的一个 $𝑚$ 元子集。Colex 编码可以把所有这样的子集连续地编号为

0, 1, \dots, (\binom{𝑁}{𝑚}) - 1 .

现在把问题向前推进一步。我们不只选择一次，而是分成 $𝐾$ 轮：第 $𝑖$ 轮选择 $𝑐_{𝑖}$ 个元素，已经选过的元素不能再次选择。每轮内部仍然不计顺序，但轮与轮之间不能交换。

例如，从 $[5]$ 中第一轮选择两个元素、第二轮选择一个元素时，

{3, 0} ∣ {4}

是一份选择结果。符号 $∣$ 只负责保留轮次边界，所以它与

{4} ∣ {3, 0}

不是同一个结果。

本文先重新理解 colex 为什么能给一次选择编号，然后在它的基础上回答：怎样给这样的多轮选择连续编号，并且从编号恢复原来的各轮集合。

Index set 与递减序列

长度为 $𝑚$ 的 index set 是 $ℕ$ 的一个 $𝑚$ 元子集；全体这样的集合记为 ${ℐ︀}_{𝑚}$ 。

每个 $𝐴 \in {ℐ︀}_{𝑚}$ 都可以唯一地按严格递减的顺序写成

𝐴 = (𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑚}), 𝑎_{1} > 𝑎_{2} > \dots > 𝑎_{𝑚} \geq 0 .

反过来，每个满足上述条件的序列也唯一确定一个 index set

{𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑚}} .

因此， ${ℐ︀}_{𝑚}$ 与所有长度为 $𝑚$ 的严格递减非负整数序列之间存在一个自然的双射。下文将通过这个双射把二者视为同一个对象：讨论集合运算时使用集合的观点，书写编码时则使用递减序列的观点。

Colex 序

两个集合 $𝐴, 𝐵$ 的对称差 $𝐴 △ 𝐵$ ，是所有只属于其中一个集合的元素组成的集合。对于两个不同的 index set，定义

𝐵 \underset{colex}{<} 𝐴 当且仅当 max (𝐴 △ 𝐵) \in 𝐴 .

也就是说，从最大的整数向下检查两个集合，第一个只属于其中一个集合的整数在哪个集合中，哪个集合就在 colex 序中靠后。这等价于从最大下标开始，按字典序比较两个集合的 0–1 特征序列，因此给出了一个全序。

Colex 编码就是前驱的数量

定义 colex 编码

𝜌_{𝑚 (𝐴)} ≔ \sum_{𝑖 = 1}^{𝑚} (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) .

这个公式最直接的解释是： $𝜌_{𝑚 (𝐴)}$ 恰好等于 $𝐴$ 在 colex 序中的前驱数量。

记 $𝒫︀ (𝐴)$ 为 $𝐴$ 的前驱集合。按照对称差最大元素的不同，将它划分为

{𝒫︀}_{𝑖 (𝐴)} ≔ {𝐵 \in 𝒫︀ (𝐴) | max (𝐴 △ 𝐵) = 𝑎_{𝑖}}, 1 \leq 𝑖 \leq 𝑚 .

这个分组条件可以画成下面的形式：

图中，浅绿色表示与 $𝐴$ 一致的固定前缀，浅蓝色表示可变部分。若 $𝐵 \in {𝒫︀}_{𝑖 (𝐴)}$ ，那么 $𝐵$ 在所有大于 $𝑎_{𝑖}$ 的整数上都与 $𝐴$ 一致，并且不包含 $𝑎_{𝑖}$ 。因此，它具有唯一的递减表示

𝐵 = (𝑎_{1}, \dots, 𝑎_{𝑖 - 1}, 𝑏_{𝑖}, \dots, 𝑏_{𝑚}), 𝑎_{𝑖} > 𝑏_{𝑖} > \dots > 𝑏_{𝑚} \geq 0 .

反过来，每个满足上述条件的递减序列都唯一确定一个 $𝐵 \in {𝒫︀}_{𝑖 (𝐴)}$ 。所以 ${𝒫︀}_{𝑖 (𝐴)}$ 与从

{0, 1, \dots, 𝑎_{𝑖} - 1}

中选取 $𝑚 - 𝑖 + 1$ 个元素的方法一一对应，于是

| {𝒫︀}_{𝑖 (𝐴)} | = (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) .

这些集合彼此不交，并且恰好覆盖 $𝒫︀ (𝐴)$ 。由加法原理，

| 𝒫︀ (𝐴) | = \sum_{𝑖 = 1}^{𝑚} | {𝒫︀}_{𝑖 (𝐴)} | = \sum_{𝑖 = 1}^{𝑚} (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) = 𝜌_{𝑚 (𝐴)} .

因此，colex 编码不是一个偶然的组合数公式：它就是 index set 在 colex 序中的秩。

Colex 给出的序同构

对于固定的 $𝑚$ ，每个 index set 都只有有限多个前驱。另一方面，固定其余各项并让 $𝑎_{1}$ 增大， $𝜌_{𝑚 (𝐴)}$ 中的

(\binom{𝑎_{1}}{𝑚})

趋于无穷，所以前驱数量没有上界。

现在任取 $𝑛 \in ℕ$ ，选一个至少有 $𝑛$ 个前驱的 $𝐴$ 。有限初始区间

𝒫︀ (𝐴) \cup {𝐴}

中的第 $𝑛 + 1$ 个元素恰好有 $𝑛$ 个前驱，因而编码为 $𝑛$ 。这说明 $𝜌_{𝑚}$ 不会跳过任何非负整数。

此外，若 $𝐵 \underset{colex}{<} 𝐴$ ，那么 $𝐵$ 的所有前驱以及 $𝐵$ 本身都是 $𝐴$ 的前驱，所以

𝜌_{𝑚 (𝐵)} < 𝜌_{𝑚 (𝐴)} .

因此编码保持 colex 序，并且不会重复。换言之，

𝜌_{𝑚} : ({ℐ︀}_{𝑚}, \underset{colex}{<}) \to (ℕ, <)

是一个序同构。

限制到 $[𝑁]$ 的 $𝑚$ 元子集时，这些集合构成 colex 序的一个有限初始区间。它们一共有 $(\binom{𝑁}{𝑚})$ 个，所以

𝜌_{𝑁, 𝑚} : ({𝐴 \subseteq [𝑁] | | 𝐴 | = 𝑚}, \underset{colex}{<}) \to ([(\binom{𝑁}{𝑚})], <)

也是一个序同构。这里

[𝑟] ≔ {0, 1, \dots, 𝑟 - 1} .

从一次选择到多轮选择

现在固定 $𝑁$ 和 $𝐾$ 个非负整数

𝑐_{1}, 𝑐_{2}, \dots, 𝑐_{𝐾}, \sum_{𝑖 = 1}^{𝐾} 𝑐_{𝑖} \leq 𝑁 .

记所有合法的多轮选择为

𝒮︀ (𝑁; 𝑐_{1}, \dots, 𝑐_{𝐾}) ≔ {𝐴_{1} ∣ \dots ∣ 𝐴_{𝐾} | 𝐴_{𝑖} \subseteq [𝑁], | 𝐴_{𝑖} | = 𝑐_{𝑖}, 𝐴_{𝑖} \cap 𝐴_{𝑗} = \emptyset when 𝑖 \neq 𝑗} .

这行记号只是把开头的问题重新写了一遍：第 $𝑖$ 轮选择 $𝑐_{𝑖}$ 个元素，不同轮选到的元素不能重复。

要数清这些结果，最自然的方向是沿着轮次向前：先选择 $𝐴_{1}$ ；确定 $𝐴_{1}$ 后再选择 $𝐴_{2}$ ；确定 $𝐴_{1} ∣ 𝐴_{2}$ 后再选择 $𝐴_{3}$ ；依此继续。

第一轮有

(\binom{𝑁}{𝑐_{1}})

种选择。选完第一轮后，无论 $𝐴_{1}$ 具体包含哪些元素，都恰好剩下 $𝑁 - 𝑐_{1}$ 个元素，所以第二轮总有

(\binom{𝑁 - 𝑐_{1}}{𝑐_{2}})

种选择。继续下去，第 $𝑖$ 轮总有

𝑟_{𝑖} ≔ (\binom{𝑁 - \sum_{ℎ < 𝑖} 𝑐_{ℎ}}{𝑐_{𝑖}})

种选择。

这里最重要的是量词的顺序：对于每一个已经确定的前缀，下一轮的具体候选内容可能不同，但候选数量总是同一个 $𝑟_{𝑖}$ 。

所以多轮选择的总数是

\prod_{𝑖 = 1}^{𝐾} 𝑟_{𝑖} = \prod_{𝑖 = 1}^{𝐾} (\binom{𝑁 - \sum_{ℎ < 𝑖} 𝑐_{ℎ}}{𝑐_{𝑖}}) .

不过，知道总数还不等于已经找到编码。下一步要做的是：把每个前缀下内容不同的候选列表，都统一编号为 $0, 1, \dots, 𝑟_{𝑖} - 1$ 。

把剩下的元素重新编号

假设前几轮已经使用了集合 $𝑈 \subseteq [𝑁]$ 。把 $𝑈$ 从 $[𝑁]$ 中删掉，再把剩余元素从 $0$ 开始依次编号。

例如取

[5] = {0, 1, 2, 3, 4}, 𝑈 = {0, 3} .

删除 $𝑈$ 后，剩余列表为

(1, 2, 4) .

重新编号就是

1 \mapsto 0, 2 \mapsto 1, 4 \mapsto 2 .

一般地，剩余元素 $𝑎$ 的新编号为

𝜅_{𝑈 (𝑎)} ≔ 𝑎 - | {𝑢 \in 𝑈 | 𝑢 < 𝑎} | .

公式右边减去的是“排在 $𝑎$ 前面、但已经被删掉的元素数量”。因此， $𝜅_{𝑈 (𝑎)}$ 就是 $𝑎$ 在剩余列表中的 0-based 位置。

这个操作是一个保序双射

𝜅_{𝑈} : [𝑁] ∖ 𝑈 \to [𝑁 - | 𝑈 |] .

它不会丢失信息：给定新编号，只要在剩余列表里取相同位置，就能恢复原来的元素。

若下一轮要选择两个元素，上例中的所有选择会被压缩成：

所以，先压缩再做 colex，可以把这一轮的三个选择依次标为 $0, 1, 2$ 。反向读取也同样直接：先由 colex rank 恢复压缩集合，再到剩余列表中按位置取出实际元素。

回到一般的第 $𝑖$ 轮。记前 $𝑖 - 1$ 轮已经使用的元素为

𝑈_{𝑖 - 1} = \cup_{ℎ < 𝑖} 𝐴_{ℎ} .

将 $𝐴_{𝑖}$ 中的每个元素按 $𝜅_{𝑈_{𝑖 - 1}}$ 压缩，得到 $𝑐_{𝑖}$ 元子集

𝐵_{𝑖} \subseteq [𝑁 - \sum_{ℎ < 𝑖} 𝑐_{ℎ}] .

再对 $𝐵_{𝑖}$ 做 colex，得到这一轮的局部编号

𝑞_{𝑖} = 𝜌_{𝑐_{𝑖}} (𝐵_{𝑖}), 0 \leq 𝑞_{𝑖} < 𝑟_{𝑖} .

注意， $𝑞_{𝑖}$ 的具体数值确实依赖前面的选择，因为压缩时使用了 $𝑈_{𝑖 - 1}$ 。不依赖前缀具体内容的是 $𝑞_{𝑖}$ 的范围：每个前缀下，它都恰好遍历 $0, 1, \dots, 𝑟_{𝑖} - 1$ 。

为什么局部编号构成笛卡尔积

先看最小的两轮例子：

[3] = {0, 1, 2}, 𝑐_{1} = 𝑐_{2} = 1 .

第一轮有 $𝑟_{1} = 3$ 个选择。选完第一轮以后只剩两个元素，所以每个第一轮结果都有 $𝑟_{2} = 2$ 个后继。所有情况可以展开成下面的表：

例如，局部编号 $(𝑞_{1}, 𝑞_{2}) = (1, 1)$ 的读取过程是：

$𝑞_{1} = 1$ 在第一轮选择 $𝐴_{1} = {1}$ ；
此时剩余列表是 $(0, 2)$ ；
$𝑞_{2} = 1$ 选择剩余列表中位置为 $1$ 的元素，所以 $𝐴_{2} = {2}$ 。

因此 $(1, 1)$ 唯一确定 ${1} ∣ {2}$ 。反过来，对 ${1} ∣ {2}$ 逐轮压缩，也会重新得到 $(1, 1)$ 。

一般情况下，可以把全部选择过程看成一棵深度为 $𝐾$ 的树。第 $𝑖 - 1$ 层的一个节点，就是一个已经确定的前缀

𝐴_{1} ∣ \dots ∣ 𝐴_{𝑖 - 1} .

每个这样的节点都有 $𝑟_{𝑖}$ 个后继，而且这些后继都被可逆地标成

0, 1, \dots, 𝑟_{𝑖} - 1 .

所以，从根走到一个叶子时，沿途记录的编号

(𝑞_{1}, 𝑞_{2}, \dots, 𝑞_{𝐾})

恰好落在

[𝑟_{1}] \times [𝑟_{2}] \times \dots \times [𝑟_{𝐾}]

中。

这个对应是双射。正向编码时，逐轮压缩并记录 $𝑞_{𝑖}$ ；反向恢复时，从第一轮开始，依次对 $𝑞_{𝑖}$ 做 colex unranking，再从当前剩余列表中取回实际元素。每一步都可逆，所以整条路径也可逆。

Mixed-radix 序

现在暂时忘掉集合，只考虑有限数字向量

𝒟︀ = [𝑟_{1}] \times [𝑟_{2}] \times \dots \times [𝑟_{𝐾}] .

其中的元素记为

𝑞 = (𝑞_{1}, 𝑞_{2}, \dots, 𝑞_{𝐾}), 0 \leq 𝑞_{𝑖} < 𝑟_{𝑖} .

把 $𝑞_{1}$ 视为最低位，把 $𝑞_{𝐾}$ 视为最高位。对两个不同向量 $𝑝, 𝑞$ ，令

𝑗 = max {𝑖 | 𝑝_{𝑖} \neq 𝑞_{𝑖}} .

定义

𝑝 \underset{mr}{<} 𝑞 当且仅当 𝑝_{𝑗} < 𝑞_{𝑗} .

也就是说，从第 $𝐾$ 位向第 $1$ 位检查，最高的不同位决定大小。

定义第 $𝑗$ 位的权重

𝑅_{1} = 1, 𝑅_{𝑗} = \prod_{𝑖 = 1}^{𝑗 - 1} 𝑟_{𝑖} (𝑗 \geq 2),

以及 mixed-radix 编码

𝜇 (𝑞) ≔ \sum_{𝑗 = 1}^{𝐾} 𝑞_{𝑗} 𝑅_{𝑗} = 𝑞_{1} + 𝑟_{1} 𝑞_{2} + 𝑟_{1} 𝑟_{2} 𝑞_{3} + \dots .

Mixed-radix 编码也是前驱的数量

记 $𝒫︀ (𝑞)$ 为 $𝑞$ 在 $\underset{mr}{<}$ 下的前驱集合。按照最高不同位 $𝑗$ ，将它划分为

{𝒫︀}_{𝑗 (𝑞)} ≔ {𝑝 \in 𝒟︀ | 𝑝_{𝑖} = 𝑞_{𝑖} for 𝑖 > 𝑗, 𝑝_{𝑗} < 𝑞_{𝑗}} .

高于 $𝑗$ 的位置必须与 $𝑞$ 相同；第 $𝑗$ 位可以取 $0, 1, \dots, 𝑞_{𝑗} - 1$ ，共有 $𝑞_{𝑗}$ 种选择；所有低位完全自由，共有

𝑟_{1} 𝑟_{2} \dots 𝑟_{𝑗 - 1} = 𝑅_{𝑗}

种选择。因此

| {𝒫︀}_{𝑗 (𝑞)} | = 𝑞_{𝑗} 𝑅_{𝑗} .

每个前驱都有唯一的最高不同位，所以这些集合彼此不交，并且恰好覆盖 $𝒫︀ (𝑞)$ 。于是

| 𝒫︀ (𝑞) | = \sum_{𝑗 = 1}^{𝐾} 𝑞_{𝑗} 𝑅_{𝑗} = 𝜇 (𝑞) .

mixed-radix 编码同样不是偶然的位权公式：它就是数字向量在 $\underset{mr}{<}$ 中的前驱数量。

$𝒟︀$ 一共有

𝑅 = \prod_{𝑖 = 1}^{𝐾} 𝑟_{𝑖}

个元素，因此

𝜇 : (𝒟︀, \underset{mr}{<}) \to ([𝑅], <)

是一个序同构。逆映射就是逐位取余：令 $𝑛_{0} = 𝑛$ ，依次计算

𝑞_{𝑖} = remainder (𝑛_{𝑖 - 1}, 𝑟_{𝑖}), 𝑛_{𝑖} = ⌊ \frac{𝑛_{𝑖 - 1}}{𝑟_{𝑖}} ⌋ .

把各轮编号拼起来

回到多轮选择。先逐轮压缩并做 colex，得到

(𝑞_{1}, 𝑞_{2}, \dots, 𝑞_{𝐾}) \in [𝑟_{1}] \times [𝑟_{2}] \times \dots \times [𝑟_{𝐾}],

再做 mixed-radix，最终编号就是

rank (𝐴_{1} ∣ \dots ∣ 𝐴_{𝐾}) = \sum_{𝑖 = 1}^{𝐾} 𝑞_{𝑖} \prod_{ℎ = 1}^{𝑖 - 1} 𝑟_{ℎ} .

因为“多轮选择 $\to$ 局部编号向量”和“局部编号向量 $\to$ 整数”都是双射，最终编码也是双射。它的值域恰好是

[𝐺], 𝐺 = \prod_{𝑖 = 1}^{𝐾} (\binom{𝑁 - \sum_{ℎ < 𝑖} 𝑐_{ℎ}}{𝑐_{𝑖}}) .

这个乘积也可以写成

𝐺 = \frac{𝑁!}{(𝑁 - \sum_{𝑖 = 1}^{𝐾} 𝑐_{𝑖})! \prod_{𝑖 = 1}^{𝐾} 𝑐_{𝑖!}} .

最后看一个完整例子。取

𝑁 = 5, (𝑐_{1}, 𝑐_{2}) = (2, 1), 𝐴_{1} = {3, 0}, 𝐴_{2} = {4} .

第一轮的 colex rank 为

𝑞_{1} = (\binom{3}{2}) + (\binom{0}{1}) = 3, 𝑟_{1} = (\binom{5}{2}) = 10 .

删除 $𝐴_{1} = {0, 3}$ 后，剩余列表是 $(1, 2, 4)$ ，所以实际元素 $4$ 被压缩为位置 $2$ 。因此

𝑞_{2} = 2, 𝑟_{2} = (\binom{3}{1}) = 3 .

最终编号为

rank ({3, 0} ∣ {4}) = 𝑞_{1} + 𝑟_{1} 𝑞_{2} = 3 + 10 \cdot 2 = 23 .

反向恢复时，先由

23 mod 10 = 3, ⌊ \frac{23}{10} ⌋ = 2

得到 $(𝑞_{1}, 𝑞_{2}) = (3, 2)$ ；再逐轮做 colex unranking，并在每一步把压缩坐标放回当前剩余列表，便恢复 ${3, 0} ∣ {4}$ 。

最终结论

从一次选择走到多轮选择，整个编码可以分成三步：

colex 给每一轮的有限子集编号；
删除已使用元素并重新编号，使不同前缀下的候选列表都变成同一个连续区间；
mixed-radix 把各轮的局部编号拼成一个整数。

Colex 与 mixed-radix 看起来是两套不同公式，但它们有同一个解释：编码值就是对象在所选顺序中的前驱数量。正因为如此，最终编号自然从 $0$ 开始，没有空缺，没有重复，并且能够反向恢复原来的多轮选择。