枚举子集 ·

2^n

· 四种算法

枚举全部子集：四种算法

幂集一页把一个集合的全部子集按大小铺开，本页换个问法：给定一个集合，用算法不重不漏地逐一生成它的全部子集。 $n$ 个元素的子集共 $2^n$ 个，因为每个元素独立地「选或不选」，两种选法相乘。下面四种算法枚举的都是这 $2^n$ 个子集，差别只在次序与视角，各有一块 board，点亮的是同一批对象。

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

1 · 二进制计数 bitmask

bitmask ·

\mathrm{mask} \in 0 \dots 2^n-1

给 $n$ 个元素编号 $0, \dots, n-1$ ，一个子集就是一串「选或不选」，也就是一个 $n$ 位二进制数 mask。让 mask 从 $0$ 数到 $2^n - 1$ ，第 $i$ 位为 $1$ 就把第 $i$ 个元素收进子集。整数与子集由此一一对应，数完全部整数即枚举出全部子集。

图 1-1 · 用整数的二进制位表示选与不选，从

0

数到

2^n - 1

即遍历全部子集。

注 · 这是四种里最省事的一种：它把「枚举子集」化归成「从 $0$ 数到 $2^n - 1$ 」，只需一个整数循环，无递归、无额外内存。工程上用一个整型的位表示一个集合、用位运算做并交差，走的就是这套对应。代价是 mask 的位序与元素的对应关系要单独记牢，弄错不会报错，只会静默地枚举出另一批子集。

2 · 逐元素递归的决策树

recursion · 每元素 2 种去处

把元素排定顺序逐个表态：第 $i$ 个元素要么不入选、要么入选，两条分支各自往下递归。递归到最后一个元素，每条决策路径恰好对应一个子集， $2^n$ 条叶子路径与 $2^n$ 个子集一一对应。这与枚举划分的逐元素递归同形，只是每个元素的去处从 $k + 1$ 个块缩成入与不入两种。

图 2-1 · 逐元素递归：每个元素分入选与不入选两支，叶子即一个子集。可单步展开递归树。

注 · 这棵二叉决策树与 bitmask 是同一件事：每条根到叶的路径就是一串「入或不入」，也就是 bitmask 里那个 $0$ 与 $1$ 的向量。区别只在遍历次序，bitmask 按整数升序，递归按深度优先，产出的集合完全相同。

3 · 迭代级联与规模翻倍

cascade · 由

\emptyset

起步逐元素翻倍

从只含空集的 $\{\emptyset\}$ 起步。每读入一个新元素 $e$ ，把已有的全部子集各复制一份、给副本加入 $e$ ，再并回集合：子集随即分成不含 $e$ 的原件与含 $e$ 的副本两半。每读入一个元素规模翻倍，读完 $n$ 个元素得到 $2^n$ 个子集。

图 3-1 · 从空集起，每读入一个元素就把已有子集复制一份并加入该元素，规模翻倍。

注 · 这一种既无递归也无位运算，只是反复复制并追加，而且天然不重：新副本一定含 $e$ ，与任何旧件都不相同。子集数 $2^n = 2 \cdot 2 \cdot \dots \cdot 2$ 的连乘结构在这个算法里最直白，每个元素给总量乘上一个 $2$ 。

4 · Gray code 的次序

Gray code · g = i ^ (i >> 1)

同样遍历 $i$ 从 $0$ 到 $2^n - 1$ ，但不直接取 $i$ 的二进制，而是取 $g = i \oplus \lfloor i/2 \rfloor$ 作为「选 / 不选」向量，写成代码即 g = i ^ (i >> 1)。二进制反射 Gray 码的性质是相邻两个 $g$ 恰好只差一个二进制位，相邻两个子集因此只差一个元素，且加入与移出各只发生一次。

图 4-1 · Gray code 次序下相邻两个子集只差一个元素。可推进观察每步变动的是哪一位。

「只差一个」的价值，要在子集上维护某个可增量更新的量时（子集和、子集异或）才显出来：从上一个子集走到下一个只需加入或移出一个元素，不必重算整份。

注 · 这一项省下的开销比预想的小，量出来才看清它真正保证的是什么。把两种次序逐步比较翻转位数：二进制计数在 $n = 8$ 时总翻位 $502$ 次、平均每步 $1.9686$ 位， $n = 16$ 时 $131054$ 次、平均 $1.9998$ 位。平均值趋于 $2$ 而不是 $n$ ，因为高位极少动。Gray 码的总翻位恰好 $2^n - 1$ ，平均每步精确的 $1$ 位。所以就平均而论只省了一半。真正的差别在最坏一步：二进制计数从 $2^{n-1} - 1$ 跨到 $2^{n-1}$ 时 $n$ 位全翻，实测 $n = 16$ 时单步最多 $16$ 位；而 Gray 码任何一步都是 $1$ 位。它还是循环的，首末两个码字实测也只差 $1$ 位。

注 · 四种算法的枚举次序各不相同，产出的集合完全一致，都是那 $2^n$ 个子集，不重不漏。其中 bitmask、逐元素递归与 Gray code 都在枚举同一批「选 / 不选」的 $0$ 与 $1$ 向量，只是遍历次序不同；迭代级联则从空集出发逐元素翻倍。枚举划分的「含最小元素的块」每一步给最小元素挑同伴，那一步枚举的就是其余元素的一个子集，用的正是本页的算法。

5 · 参考文献

Gray code. Wikipedia. 二进制反射 Gray 码的构造 $g = i \oplus \lfloor i/2 \rfloor$ 与它的循环性质。https://en.wikipedia.org/wiki/Gray_code
Power set. Wikipedia. 子集总数 $2^n$ 与幂集的基数。https://en.wikipedia.org/wiki/Power_set
Combination. Wikipedia. 按大小分层的子集个数与二项式系数。https://en.wikipedia.org/wiki/Combination