枚举划分 · Bell 数 Bₙ

枚举全部划分：三种算法

划分一页只校验你给出的分块是否合法；这一页反过来：给定一个集合，不重不漏地列出它的全部划分。n 个元素的划分总数是 Bell 数 $B_n$ （1, 1, 2, 5, 15, 52, …），增长比幂集的子集数 ${2^n}$ 还猛。下面三种算法都能枚举出这 $B_n$ 个划分，差别只在枚举的次序与视角——每种算法各有一块 board，点亮的是同一批划分，只是次序与节奏不同。用全部播放可让三种算法从头同步开跑，直观对比它们的推进方式。

1 · 逐元素递归：每个元素「进老块或开新块」

recursion · 每元素 |blocks| + 1 种去处

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

算法骨架 · 伪代码

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

为什么不重不漏：每个元素恰好被指派一次去处，不同的决策序列给出不同的指派，故不同路径必是不同划分；而任何一个划分，都能被「把每个元素放进它所属的块」这条唯一路径生成——于是 $B_n$ 条叶子路径与 $B_n$ 个划分一一对应。

2 · restricted growth string：用合法编号串对应划分

RGS · a[0] = 0 · a[i] ≤ 1 + max(a[0..i−1])

用一个长度 n 的数组 a 记录「第 i 个元素属于第几号块」。合法性只有一条约束：a[0] = 0，且 $a[i] \le 1 + \max (a[0..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) 开始

约束在拦什么：若允许 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, ∅) 开始

子集枚举来自哪：固定最小元素后，「其余剩余元素里哪些与它同块」有 2^|rest| 种选法，正是 rest 的幂集（见幂集 P(A)）。这一步把「造一块」化归为「选一个子集」，划分的枚举便递归到更小的集合上。

三法同源：三种算法产出的次序各不相同，但产出的集合完全一致——都是那 $B_n$ 个划分，不重不漏。划分与等价关系一一对应（见商集 A/R）；工程上，GROUP BY 与并查集的连通分量，正是在求某个等价关系诱导的那个划分。真要按规模枚举全部划分时，RGS 因为只维护一个整型数组、天然按字典序推进，最常被用作生成器。

4 · 约束划分：按条件筛，块数落在 Stirling 数

constrained · 恰好 k 块 = S(n, k)

前面三种算法把 $B_n$ 个划分全列了出来。实际问题常只关心满足某条件的划分：分成恰好 k 组、每组不少于 m 个。把条件加在全划分上，命中的点亮、其余压暗。最有用的一条是块数：分成恰好 k 块的划分数正是 Stirling 第二类数 S(n, k)，而 $B_n = S(n, 1) + S(n, 2) + \dots + S(n, n)$ ——Bell 数就是各 k 的 Stirling 数之和。

为什么块数对应 Stirling：S(n, k) 的递推 $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 与数独。

5 · 相关链接

Partition of a set · en.wikipedia.org——划分的定义、与等价关系的一一对应，以及计数。
Bell number — Bₙ · en.wikipedia.org——划分总数 $B_n$ 、Bell 三角递推与 Bₙ = Σ C(n,k)·B_{n−k} 等关系。
Restricted growth string · en.wikipedia.org——用编号串表示划分的标准编码，以及按字典序生成全部划分的算法。