快速枚举二进制子集的方法

Posted on 2018-10-07 Views:

简介

目标：对于一个位二进制表示的子集x，我们希望枚举其子集。

朴素枚举其子集的代码，复杂度 $O(2^{n})$ ：

for (int s = 0; s <= x; s++)
    if (s | x == x)
        // s 表示的二进制是x的子集

快速枚举其子集的代码，复杂度 $O(2^{|X|})$ ，其中是x表示的集合：

for (int s = x; s > 0; s = (s - 1) & x)
    // s表示的二进制是x的子集
// 以上算法不！会！处！理！空！集！，额外处理！

正确性证明：

代码中的& x保证s一定是s的子集，而(s - 1)保证枚举出来的s递减至0，详细证明不在此赘述~~脑补即可~~.

在很多的状压DP当中，我们不仅要枚举一个集合的子集，而是要枚举 [0, 2^n) 的所有二进制数表示的集合的子集，如果使用朴素地暴力做法，那么复杂度显然是 O(4^n) ，可以过 $n \le 10$ 的数据。

那么如果我们使用刚刚介绍的优化方法，复杂度会变成多少呢？

分析：总体复杂度为：

$\sum_{i = 0}^n \binom{n}{i}2^i = \sum_{i = 0}^n \binom{n}{i}2^i1^{n - i}$

逆用二项式定理：

$\sum_{i = 0}^n \binom{n}{i}2^n = (2 + 1)^n = 3^n$

因此，算法的复杂度为

（而且是最优的），可以通过 $n \le 15$ 的数据。