数据结构与算法 / 系统课时

枚举子集完成集合状态转移

枚举子集完成集合状态转移

很多集合 DP 的一个状态并不是从“删掉一个元素”转移,而是要把当前集合拆成两个部分,并尝试所有子集。逐个扫描 0..mask 会浪费大量无效候选,本节用 (sub - 1) & mask 只枚举 mask 的真实子集,并解释总复杂度为何常写成 O(3n)O(3^n)。

学习目标

  • 掌握非空子集的标准位运算枚举写法。
  • 理解 (sub - 1) & mask 为什么能跳到下一个子集。
  • 推导“外层枚举集合、内层枚举子集”出现 3n3^n 的原因,并判断规模是否可接受。

只枚举当前集合真正拥有的子集

假设 mask = 0b10110,其中只有第 1、2、4 位可被选入子集。一个简单但低效的办法是遍历 0..mask,再判断候选是否满足 sub & mask == sub。这样会检查许多包含非法位的整数。

标准写法从 sub = mask 开始,每次执行 sub = (sub - 1) & mask。sub - 1 会改变当前低位结构,而再与 mask 做按位与,会清除所有不属于原集合的位。于是得到的始终是 mask 的子集,而且不会重复。

python
def submasks(mask):
    result = []
    sub = mask

    # 循环内只产生非空子集;空集可在循环后单独处理。
    while sub:
        result.append(sub)
        sub = (sub - 1) & mask

    return result


mask = 0b10110
for sub in submasks(mask):
    print(f"{sub:05b}")

预期输出

text
10110
10100
10010
10000
00110
00100
00010

这里 mask 含有 3 个有效元素,因此非空子集恰好有 23−1=72^3 - 1 = 7 个。若转移必须包含空集,可以在循环结束后额外处理 sub = 0,不要把循环条件直接改成永真,否则会在 0 处重复。

把子集枚举放进 DP 转移

集合拆分型 DP 常见的抽象形式是 dp[mask] = min(dp[mask ^ sub] + cost[sub])。其中 sub 表示从 mask 中拿出的一组元素,mask ^ sub 是剩余部分。由于 sub 保证属于 mask,这里异或与“从集合中删除这些元素”效果一致。

下面是片段示例,依赖已经初始化好的 dp、cost 和当前状态变量 mask:

python
sub = mask
while sub:
    rest = mask ^ sub
    dp[mask] = min(dp[mask], dp[rest] + cost[sub])
    sub = (sub - 1) & mask

这类写法常用于分组、集合划分、选择若干元素一次处理等问题。是否允许 sub = mask、是否允许空集,以及两个部分是否有顺序,都必须根据题意决定,不能机械套公式。

为什么总复杂度是三的幂

只看一个固定 mask,若它有 k 个元素,需要枚举 2k2^k 个子集。但如果外层还要遍历所有 mask,不能简单写成 2n⋅2n=4n2^n · 2^n = 4^n,因为小集合的子集数远少于 2n2^n。

从单个元素的归属看,在一对 (mask, sub) 中它只有三种合法状态:

元素状态 是否在 mask 是否在 sub
不属于当前集合 否 否
属于 mask 但不属于 sub 是 否
同时属于 mask 和 sub 是 是

每个元素独立有 3 种选择,因此全部 (mask, sub) 组合总数是 3n3^n。这也说明“枚举所有集合,再枚举其所有子集”的典型复杂度是 O(3n)O(3^n)。如果每次转移内部还做额外的 O(n)O(n) 工作,总复杂度还要再乘相应因子。

先用元素规模判断能不能做

3n3^n 增长很快。n = 15 时约有 1430 万个 (mask, sub) 组合,经过常数优化后通常仍有机会;n = 20 时已经超过 34 亿,纯粹的全量枚举通常不可接受。

所以看到“对子集再枚举子集”时,应先检查约束,再决定是否需要减少状态、限制候选子集、预计算有效集合,或者换成别的转移方式。

子集枚举的价值在于把候选空间限制在真实可用的集合上。掌握 (sub - 1) & mask 后,更重要的是先算清楚它被调用多少次:位运算常数很小,但指数级状态数量仍然决定算法能处理的上限。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

枚举子集完成集合状态转移

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通