将集合 $S$ 中的元素编号为 $0, 1, \cdots, |S| - 1$,可用一个非负整数 $x$ 表示集合 $S$ 的一个子集 $S_x$,$x$ 的二进制第 $i$ 位(由低到高)为 $1$ 表示子集 $S_x$ 包含集合 $S$ 的第 $i$ 个元素,否则表示不包含。$S$ 自身可用全 $1$ 表示
朴素枚举
要枚举 $S_x$ 的子集,即枚举 $x$ 中的 $1$ 位置的组合。显然,若 $S_y \subseteq S_x$,则 $y \le x$。因此可枚举小于等于 $x$ 的每个非负整数 $i$,判断 $i$ 中 $1$ 的位置在 $x$ 中是否也为 $1$
#include <cstdio>
void print_binary(int x) {
for (int i = 7; i >= 0; i --) {
if (i == 3) printf(" ");
printf("%d", x >> i & 1);
}
puts("");
}
// return 1 if x is a subset of s
bool is_subset(int s, int x) {
for (int i = 7; i >= 0; i --)
if ((x >> i & 1) && !(s >> i & 1))
return 0;
return 1;
}
void enumerate_subsets(int s) {
for (int x = s; x >= 0; x --)
if (is_subset(s, x)) print_binary(x);
}
int main() {
enumerate_subsets(0b101100);
return 0;
}
上面的代码输出如下,$(101100)_2$ 包含 $3$ 个 $1$,每个 $1$ 可选可不选,有 $2^3 = 8$ 种可能
0010 1100
0010 1000
0010 0100
0010 0000
0000 1100
0000 1000
0000 0100
0000 0000
判断优化
实际上,要判断 $x$ 是否是 $s$ 的子集,并不需要遍历 $x$ 的所有位,只要判断 $x\ \\&\ s$ 是否等于 $x$。因为与运算会去除 $x$ 中那些未出现在 $s$ 相应位置上的 $1$,而保留位置相同的 $1$
// return 1 if x is a subset of s
bool is_subset(int s, int x) {
return (s & x) == x;
}
去除冗余
进一步观察,在遍历找到的两个相邻子集之间,存在很多无效 $x$
void enumerate_subsets(int s) {
for (int x = s; x >= 0; x --) {
if (is_subset(s, x)) printf("-");
else printf(" ");
print_binary(x);
}
}
int main() {
enumerate_subsets(0b101100);
return 0;
}
以上代码输出如下。这些无效 $x$ 的值均大于下一个有效 $x$,而下一个有效 $x$ 等于 $(x - 1)\ \\&\ s$。因为 $x - 1$ 会让 $x$ 最后一个 $1$ 变为 $0$,后面所有 $0$ 变为 $1$。和 $s$ 进行与运算后,相当于组合时,不选最后一个 $1$,而选择这个 $1$ 后面的所有在 $s$ 中出现的 $1$。它是不选最后一个 $1$ 形成的子集中最大的数,因此不会漏解
-0010 1100
0010 1011
0010 1010
0010 1001
-0010 1000
0010 0111
0010 0110
0010 0101
-0010 0100
0010 0011
0010 0010
0010 0001
-0010 0000
0001 1111
0001 1110
0001 1101
0001 1100
0001 1011
0001 1010
0001 1001
0001 1000
0001 0111
0001 0110
0001 0101
0001 0100
0001 0011
0001 0010
0001 0001
0001 0000
0000 1111
0000 1110
0000 1101
-0000 1100
0000 1011
0000 1010
0000 1001
-0000 1000
0000 0111
0000 0110
0000 0101
-0000 0100
0000 0011
0000 0010
0000 0001
-0000 0000
基于此规律,可让 $x$ 直接跳到下一个有效 $x$,不必每次减 $1$
void enumerate_subsets(int s) {
for (int x = s; x; x = x - 1 & s)
print_binary(x);
}
int main() {
enumerate_subsets(0b101100);
return 0;
}
以上代码输出如下。注意空集需要手动枚举,否则循环无法结束
0010 1100
0010 1000
0010 0100
0010 0000
0000 1100
0000 1000
0000 0100
时间复杂度
若 $s$ 中有 $k$ 个 $1$,由乘法原理,它的子集数是 $2^k$,由于上述做法不存在冗余遍历,因此时间复杂度是 $O(2^k)$
枚举 $1 \sim 2^n - 1$ 中每个数的所有子集
for (int i = 1; i < 1 << n; i ++)
for (int j = i; j; j = j - 1 & i)
print_binary(j);
直观来看,对于有 $i$ 个 $1$ 的二进制数字,需要 $2^i$ 的时间。而有 $i$ 个 $1$ 的二进制数字有 $C(n, i)$ 个,所以整段代码的时间为
$$ \sum_{i = 0}^{n} C(n, i) \cdot 2^i $$
由二项式定理
$$ (1 + x)^n = \sum_{i = 0}^{n} C(n, i) x^i $$
令 $x = 2$ 有
$$ \sum_{i = 0}^{n} C(n, i) \cdot 2^i = 3^n $$
因此,上述代码的时间复杂度是 $O(3^n)$
“以上代码输出如下。这些无效 x 的值均小于下一个有效 x”这里是不是错了?这是无效的 0010 1011,这是下一个有效的-0010 1000??
应该是大于,已改正。