子集生成

简介

枚举所有子集

枚举$0$到$2^n-1$中的每个数字$i$，然后将数字$i$转化为二进制，
如果$i$的第$j$位是$1$，表示集合$i$包含$j$；
如果$i$的第$j$位是$0$，表示集合$i$不包含$j$。
下面这段代码可以从小到大枚举$\{0, 1, \ldots, n - 1\}$的所有子集

void solve(int n)
{
    for (int i = 0; i < 1 << n; i++)
    {
        printf("正在枚举集合i i=%d\n", i);
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                printf("集合i包含数字j i=%d j=%d\n", i, j);
            }
            else
            {
                printf("集合i不包含数字j i=%d j=%d\n", i, j);
            }
        }
    }
}

枚举固定大小的子集

枚举大小为$k(k > 0)$的子集，初始化$i = 2^k - 1$为最小的满足条件的集合。
计算x = lowbit(i)和y = i + x。
由于进位，y的二进制可能包含比i更少的1。
(i & ~y)可以得到除了x所有进位的位置，显然这些位置一定是连续的1。
接下来除以x，除以2（也可以写成右移1位）可以删去所有连续的1右侧的0。
再和y按位或，便可以得到下一个，恰好包含k个1的子集。
下面这段代码可以从小到大枚举$\{0, 1, \ldots, n - 1\}$的所有大小为$k$的子集

void solve(int n, int k) {
    for(int i = (1 << k) - 1; i < (1 << n);) {
        // ... i
        int x = i & -i, y = i + x;
        i = (((i & ~y) / x ) >> 1) | y;
    }
}

11001110   i
00000010   i & -i = lowbit(i)
11010000   i + lowbit(i) = y
00101111   ~y
00001110   i & ~y
00000111   (i & ~y) / x
00000011   ((i & ~y) / x) >> 1
11010011   ((i & ~y) / x) >> 1 + y

枚举子集

初始i = x，之后每次i = (i - 1)但是这个的结果可能包含x没有的元素
所以执行i = (i - 1) & x即可枚举所有子集，
最后结束条件是i == 0，如果i == 0就推出。
下面这段代码可以从大到小枚举$x$所有的子集

void solve(int n) {
    for (int i = x;; i = (i - 1) & x) {
        // ... i
        if (i == 0) {
            break;
        }
    }
}

枚举超集

枚举超集和枚举子集思路基本一样，只是把$-1$变成了$+1$，把按位与变成了按位或。
下面这段代码可以从小到大枚举$x$所有的超集

void solve(int n, int x) {
    for (int i = x; i < 1 << n; i = (i + 1) | x) {
        // ... i
    }
}

参考题目

Luogu P1036
枚举大小为$k$的所有子集。

uoj 300
Lucas定理，然后枚举子集。

参考资料

枚举子集

枚举子集

枚举子集的子集

枚举固定大小的子集（枚举组合）

练习题

abc159_e Dividing Chocolate

https://atcoder.jp/contests/abc159/tasks/abc159_e

参考代码

题解