二进制子集枚举

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

二进制子集枚举

作者：

美琴 , 2022-07-31 19:47:10 , 所有人可见 , 阅读 410

将集合 $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$ 种可能

判断优化

实际上，要判断 $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$ 形成的子集中最大的数，因此不会漏解

基于此规律，可让 $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;
}

以上代码输出如下。注意空集需要手动枚举，否则循环无法结束

时间复杂度

若 $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)$

例题

AcWing 529. 宝藏

延申

有元素个数限制的子集枚举 - Gosper’s Hack

参考

2 评论

xrandx 2022-11-19 10:30

“以上代码输出如下。这些无效 x 的值均小于下一个有效 x”这里是不是错了？这是无效的 0010 1011，这是下一个有效的-0010 1000？？

美琴 2023-09-03 06:34

应该是大于，已改正。

App 内打开