rank / unrank · O(k)

组合数系统：给每个组合一个编号

从 $n$ 个元素里取 $k$ 个共 $C(n, k)$ 种。把这些子集与 $0$ 到 $C(n, k) - 1$ 的整数一一对应起来，组合就有了编号：rank 把子集映成整数，unrank 反向解码。这是康托展开在组合上的对偶，康托展开编号的是 $n!$ 个排列，本页编号的是 $C(n, k)$ 个子集。有了这层映射，随机取一个组合退化成取一个随机整数，把组合存进数据库退化成存一个整数，枚举也可以按编号区间切开并行。

1 · 字典序下的分段累加

把子集写成递增序列 $c_1 < c_2 < \dots < c_k$ ，取值在 $0$ 到 $n-1$ 之间，按字典序排好。排在它前面的子集可以按「第一个不同的位置」分类：若某个子集在第 $i$ 位首次变小，前 $i-1$ 位与它相同，第 $i$ 位取某个 $a$ 满足 $c_{i-1} < a < c_i$ ，后面 $k-i$ 位再从 $a+1$ 到 $n-1$ 里任选。各类相加得

\mathrm{rank} = \sum_{i=1}^{k} \sum_{a=c_{i-1}+1}^{c_i-1} \binom{n-1-a}{k-i}, \qquad c_0 = -1

内层是一段连续的二项式系数求和，可以用 Pascal 三角的行求和（hockey stick）折成一项，整个式子随之塌成一层循环：

\mathrm{rank} = \binom{n}{k} - 1 - \sum_{i=1}^{k} \binom{n-1-c_i}{k-i+1}

两版给出同一个数，朴素版每步扫一遍候选，代价 $O(nk)$ ；闭式版每步只算一次二项式系数，代价 $O(k)$ 。逆向的 unrank 仍走朴素形状：从最小的候选开始，逐个减去以它开头的子集个数 $\binom{n-1-a}{k-i}$ ，减不动时这一位就定下来。

2 · 组合数系统的唯一表示

combinatorial number system · N = C(cₖ,k) + … + C(c₁,1)

换一个视角，编号可以脱离 $n$ 而存在。每个非负整数 $N$ 都有唯一一种写法

N = \binom{c_k}{k} + \binom{c_{k-1}}{k-1} + \dots + \binom{c_1}{1}, \qquad c_k > c_{k-1} > \dots > c_1 \ge 0

这就是组合数系统（combinatorial number system）：位权不是 $10^i$ 或 $i!$ ，而是二项式系数，第 $i$ 位的数字 $c_i$ 直接就是子集的第 $i$ 小元素。它编的是递减序（colex）下的名次，与 $n$ 无关， $n$ 只决定编号用到多大。

定理 2.1 固定 $k \ge 1$ ，映射 $(c_1, \dots, c_k) \mapsto \sum_{i} \binom{c_i}{i}$ 是严格递减序列集合到非负整数的双射。

证明关键是一条上界：若最高位满足 $c_k \le C - 1$ ，则各位至多取到 $c_i \le C - 1 - (k - i)$ ，代入得

\sum_{i=1}^{k} \binom{c_i}{i} \le \sum_{i=1}^{k} \binom{C-1-k+i}{i} = \binom{C}{k} - 1 < \binom{C}{k}

即最高位一旦压低一档，整个和就跌破 $\binom{C}{k}$ ，追不回来。所以满足 $\binom{c_k}{k} \le N$ 的最大 $c_k$ 是唯一可能的选择；定下 $c_k$ 后对 $N - \binom{c_k}{k}$ 与 $k-1$ 重复同一论证，逐位唯一。∎

unrank 因此就是贪心：从 $i = k$ 到 $1$ ，每步在 Pascal 三角的第 $i$ 斜列上找最大的 $c_i$ 使 $\binom{c_i}{i}$ 不超过剩余量，减掉，进入下一位。取 $N = 1000000$ 、 $k = 5$ 实测得 $962598 + 35960 + 1330 + 105 + 7$ ，对应子集 $\{7, 15, 21, 32, 43\}$ 。

图 2-1 · 编号与组合的双向面板。可拖动

n

、

k

与编号滑块看子集在格子上如何点亮，也可直接点格子改子集读出它的编号；下方表格是贪心分解的逐步剩余量与减去的二项式系数。切换开关可对照字典序与组合数系统两套编号。

3 · 两套编号的镜像

同一个子集在两套口径下的编号并不相等。 $n = 8$ 、 $k = 3$ 时子集 $\{1, 3, 6\}$ 的字典序 rank 是 $28$ ，组合数系统 rank 是 $24$ 。两个数并排打印出来时像是有一边实现错了，实际都对：字典序从小到大先比第一个元素，组合数系统先比最大的元素，排序口径本就不同。

把地面集翻转 $a \mapsto n-1-a$ 、再把编号翻转 $N \mapsto \binom{n}{k} - 1 - N$ ，两者就对上了：

\mathrm{rank}_{\text{lex}}(S) = \binom{n}{k} - 1 - \mathrm{rank}_{\text{CNS}}(\{\,n-1-a : a \in S\,\})

$\{1, 3, 6\}$ 翻转成 $\{1, 4, 6\}$ ，其组合数系统 rank 为 $27$ ，而 $C(8,3) - 1 - 27 = 28$ 。这条等式对 $n \le 12$ 的全部 $(n, k)$ 与全部子集逐个校验通过。选哪一套取决于需求：要与字典序枚举对齐就用前者，要一个不依赖 $n$ 的稳定编号就用后者。

4 · 编号宽度的上限

编号是整数，整数有宽度。坑不在 $\binom{n}{k}$ 本身有多大，而在算它的过程。

警示 · 本系列的 comb 是浮点连乘 r = r * (n - i) / (i + 1)，中间积比最终结果大二十倍上下。中间积第一次越过 Number.MAX_SAFE_INTEGER 是在 $(n, k) = (52, 24)$ ，此时 $C(52, 24) = 426\,384\,982\,032\,100$ 还不到安全整数上限的 $5\%$ ，结果仍精确。第一个真正算错的是 $C(56, 23)$ ：返回 $3\,167\,295\,784\,216\,201$ ，真值 $3\,167\,295\,784\,216\,200$ ，大 1。而 $\binom{n}{k}$ 自身要到 $C(57, 25) = 9\,929\,472\,283\,517\,787$ 才越过安全整数。后果落在越界检查上：unrankCombination 拿这个大了 1 的值当上界，真正越界的输入 $3\,167\,295\,784\,216\,200$ 被放行，贪心一路减到候选耗尽，返回的数组只有 22 个元素而非 23 个。

$k = 1$ 时编号上限就是 $n$ ， $k$ 取到 $n/2$ 时 $\binom{n}{k}$ 增长最快。要在 $n$ 更大的场合编号，得换精确算法，见 C(n, k) 的计算；均匀抽样对 unrank 的用法见均匀抽样；贪心每一步落在 Pascal 三角哪一行，见 Pascal 三角与二项式定理与组合 C(n, k)。

5 · 参考文献

Knuth, D. E. (2011). The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. §7.2.1.3.
Combinatorial number system. Wikipedia. 组合数系统的定义、唯一性与 unrank 贪心。https://en.wikipedia.org/wiki/Combinatorial_number_system
Combination. Wikipedia. 组合的枚举顺序与编号。https://en.wikipedia.org/wiki/Combination
Hockey-stick identity. Wikipedia. 连续二项式系数求和折成一项的恒等式。https://en.wikipedia.org/wiki/Hockey-stick_identity