枚举划分 · Bell 数

B_n

枚举全部划分：三种算法

划分与等价关系一节只校验给定的分块是否合法，本页反过来：给定一个集合，不重不漏地列出它的全部划分。 $n$ 个元素的划分总数是 Bell 数 $B_n$ ，前几项为 $1, 1, 2, 5, 15, 52, 203, \dots$ 。三种算法枚举的都是这 $B_n$ 个划分，差别在次序、视角与代价。

图 0-1 · 三种生成算法共用的控制面板：选集合大小与算法，board 上按该算法的次序逐一点亮划分。

1 · 逐元素递归

recursion · 每元素

k + 1

种去处

把元素排定顺序逐个放入。第一个元素单独成块；此后每个元素面对当前的 $k$ 个块，有 $k + 1$ 种去处：加进任一个已有块，或自己新开一块。递归到最后一个元素，每条决策路径对应一个划分。

算法骨架 · 伪代码

partitions(elements):
  rec(i, 当前划分 blocks):
    若 i 已越过最后一个元素 → 记下 blocks，返回
    e ← 第 i 个元素
    对 blocks 里每个已有块 → 把 e 放进这一块，递归 rec(i+1, …)
    另外              → 让 e 单独新开一块，递归 rec(i+1, …)
  从 rec(0, ∅) 开始

图 1-1 · 逐元素递归：每个元素要么进已有的块，要么开一个新块。可单步推进观察递归树的展开。

不重不漏可以直接论证：每个元素恰被指派一次去处，不同的决策序列给出不同的指派，故不同路径必是不同划分；反过来任一划分都能被「把每个元素放进它所属的块」这条唯一路径生成。于是 $B_n$ 条叶子路径与 $B_n$ 个划分一一对应。

2 · restricted growth string

RGS ·

a_0 = 0

a_i \le 1 + \max(a_0, \dots, a_{i-1})

用一个长度 $n$ 的数组 $a$ 记录「第 $i$ 个元素属于第几号块」。合法性只有一条约束： $a_0 = 0$ ，且 $a_i \le 1 + \max(a_0, \dots, a_{i-1})$ ，即新块的编号只能比已用过的最大编号大 $1$ 。按此约束枚举全部合法数组，即与全部划分一一对应。这串数组称作 restricted growth string。

算法骨架 · 伪代码

partitions(elements):
  a ← 长度 n 的块号数组
  fill(i, used):               // used = 已用块数 = 1 + max(a[0..i−1])
    若 i == n → 按相同块号把元素分组，记下划分，返回
    对 v 从 0 到 used:           // 取 used = 新开一块，取更小的 = 并入老块
      a[i] ← v
      fill(i+1, max(used, v+1))
  从 fill(0, 0) 开始

图 2-1 · restricted growth string 与划分的一一对应。可推进编号串，观察合法性约束如何限制取值。

注 · 那条约束拦的是换名重复。若允许 $a$ 取任意编号，划分「 $\{1, 3\}$ 与 $\{2\}$ 」会既写成 $(0, 1, 0)$ 又写成 $(1, 0, 1)$ ，被数两次。 $a_i \le 1 + \max(\dots)$ 强制块按首次出现的顺序编号，给每个划分钉死唯一的编号串。这也让枚举天然按字典序推进，是它常被选作生成器的原因。

3 · 含最小元素的块

block-of-min · 每步枚举 rest 的子集

每一步盯住剩余元素里最小的那个，让它来定义当前这一块：从其余剩余元素中任选一个子集与它同块，构成一块，再对剩下的元素递归。每个块都由其最小元素唯一确定，且块按最小元素升序产出，故每个划分恰被数到一次。

算法骨架 · 伪代码

partitions(pool, 已完成的块 blocks):
  若 pool 为空 → 记下 blocks，返回
  first ← pool 里最小的元素       // 由它定义下一块
  rest  ← pool 去掉 first
  对 rest 的每个子集 S:           // 子集 = rest 的幂集
    新块 ← {first} ∪ S
    partitions(rest − S, blocks + [新块])
  从 partitions(elements, ∅) 开始

图 3-1 · 每步为最小剩余元素挑选同伴的生成方式。可单步观察块如何逐个封闭。

固定最小元素后，「其余剩余元素里哪些与它同块」共有 $2^{|\text{rest}|}$ 种选法，即 rest 的幂集。这一步把「造一块」化归为「选一个子集」，用的就是枚举子集那一页的算法。

4 · 三种算法的代价

cost · 递归调用次数

三者产出相同，工作量不同。把递归调用次数数出来，差别是结构性的，不是常数因子的抖动。

注 · 逐元素递归与 RGS 的调用次数逐项完全相同： $n$ 从 $1$ 到 $9$ 依次是 $2, 4, 9, 24, 76, 279, 1156, 5296, 26443$ 。原以为 RGS 靠整型数组记账会省下一些，实测一次不省——两者是同一棵递归树，只是节点上存的东西不同。这串数恰是 Bell 数的前缀和 $\sum_{i=0}^{n} B_i$ （ $n = 9$ 时 $1 + 1 + 2 + 5 + 15 + 52 + 203 + 877 + 4140 + 21147 = 26443$ ），因为深度 $i$ 处的状态就是前 $i$ 个元素的划分，共 $B_i$ 个。

含最小元素的块则另成一路：调用次数是 $2 B_n$ ，逐项精确， $n = 4$ 时 $30 = 2 \times 15$ ， $n = 9$ 时 $42294 = 2 \times 21147$ ；内层的子集枚举步数是 $2 B_n - 1$ 。于是它比前两者贵将近一倍： $n = 9$ 时 $42294$ 对 $26443$ 。渐近上差距还会略微拉大，因为 $\sum_{i \le n} B_i / B_n \to 1$ （ $B_{n-1}/B_n \to 0$ ），前两者的调用数趋近叶子数，而这一种恒为叶子数的两倍。三种算法在 $n \le 9$ 上产出个数均等于 $B_n$ ，已逐项核对。

5 · 约束划分与 Stirling 数

constrained · 恰好

k

块即

S(n, k)

实际问题常只关心满足某条件的划分：分成恰好 $k$ 组、每组不少于 $m$ 个。最有用的一条是块数：分成恰好 $k$ 块的划分数是第二类 Stirling 数 $S(n, k)$ ，而 $B_n = \sum_{k=1}^{n} S(n, k)$ 。

图 5-1 · 按块数筛选划分，计数落在第二类 Stirling 数上。可调块数观察筛出的数量。

块数之所以对应 Stirling 数，看递推即明： $S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)$ 的两项，正是逐元素递归里第 $n$ 个元素的两种去处——并入已有 $k$ 块之一（ $k$ 种，块数不变），或自己新开一块（块数由 $k-1$ 升到 $k$ ）。对 $k$ 求和即得 $B_n$ 。

注 · 本页的块可以是任意子集。若反过来只允许某个给定的子集族充当块、要用它们恰好拼出全集，那是精确覆盖（exact cover）问题，与本页的枚举不是一回事，见 Dancing Links 与数独。划分与等价关系的一一对应见定理 3.1；工程上 GROUP BY 与并查集的连通分量，求的都是某个等价关系诱导的那个划分。

6 · 参考文献

Bell number. Wikipedia. Bell 数的递推、Bell 三角与渐近增长。https://en.wikipedia.org/wiki/Bell_number
Partition of a set. Wikipedia. 划分的定义与它和等价关系的对应。https://en.wikipedia.org/wiki/Partition_of_a_set
Stirling numbers of the second kind. Wikipedia. $S(n, k)$ 的递推、显式公式与它对 Bell 数的求和。https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
Knuth, D. E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, §7.2.1.5. Addison-Wesley. restricted growth string 与集合划分的生成算法。