集合与二进制

前面的代码里(【开关问题】POJ 3276 3279 3185 1222)可以看到一些为了枚举所有状态用到了集合的整数表现与位操作。

虽然位操作枚举比较简单但是这种方法只能在元素比较少的情况下(20个左右)使用。

假设集合有$N$个元素,依次给它们编号$0, 1, \cdots, N-1$,由于每个元素在集合中只有两种状态:存在或者不存在。那么可以令相应二进制位来表示,存在则为1,否则为0。

举个例子,8个元素编号依次为$0, 1, \cdots, 7$,那么编号为$\lbrace 0, 2, 4\rbrace $的集合可以用$S = (00010101)_2 = (21)_{10} % 注意下标$来表示。那么空集$\varnothing$可用$S = (00000000)_2 = (0)_{10}$来表示(即都不存在),同理全集可用$S=(11111111)_2 = (255)_{10} = 2^8 - 1$表示。

集合的操作

像这样表示之后,一些集合运算就可以对应地写成如下方式:

操作 方式
空集$\varnothing$ 0
全集$\lbrace 0, 1, \cdots, N-1\rbrace $ (1<<N)-1
只含有第$i$个元素的集合$\lbrace i\rbrace $ 1<<i
判断第$i$个元素是否属于集合$S$ if(S>>i & 1)
向集合中加入第$i$个元素$S\cup \lbrace i\rbrace $ S|1<<i
从集合中去掉第$i$个元素$S\backslash \lbrace i\rbrace $ S&~(1<<i)
集合$S$和$T$的并集$S\cup T$ S|T
集合$S$和$T$的交集$S\cap T$ S&T

实例

准备看学妹推荐的电影《战长沙》,原来是电视剧算了继续更,算了每天就看一集吧,一集时间也太长了。。

枚举所有子集

要将集合$\lbrace 0, 1, \cdots, n-1\rbrace$的所有子集都枚举出来的话,可以这样:

for(int S=0; S<1<<N; ++S) {
    // ...
}

$S$从空集开始,然后按照$\lbrace 0 \rbrace, \lbrace 1 \rbrace, \lbrace 0, 1 \rbrace, \cdots, \lbrace 0, 1, \cdots, N-1 \rbrace $的升序顺序枚举出来。

测试代码

void print_set(int Subset, const char *uSet) {
    int N = strlen(uSet);
    printf("{");
    for(int i=0; i<N; ++i)
        if(Subset&1<<i) printf("%c,", uSet[i]);
    if(Subset != 0) printf("\b");
    printf("}\n");
}

int main() {
    char Set[] = "ABC";
    puts("集合{A, B, C}的所有子集:");
    int N = strlen(Set);
    for(int S=0; S<1<<N; ++S)
        print_set(S, Set);
}

输出结果

集合{A, B, C}的所有子集:
{}
{A}
{B}
{A,B}
{C}
{A,C}
{B,C}
{A,B,C}

枚举某个集合sup的所有子集

int sub = sup;
do {
    // ...
    sub = (sub-1) & sup;
} while(sub != sup); // 当sub = 0的时候,有sub = (-1 & sup) = sup

测试代码

int main() {
    char Set[] = "ABCDEF";
    int sup = 11; // 001011
    puts("sup集合元素为:");
    print_set(sup, Set);
    puts("其所有子集为:");
    int sub = sup;
    do {
        print_set(sub, Set);
        sub = (sub-1) & sup;
    } while(sub != sup); // 当sub = 0的时候,有sub = (-1 & sup) = sup
    return 0;
}

输出结果

sup集合元素为:
{A,B,D}
其所有子集为:
{A,B,D}
{B,D}
{A,D}
{D}
{A,B}
{B}
{A}
{}

枚举所有大小为k的子集

int comb = (1<<k) - 1;
while(comb < 1<<N) {
    // ...
    int x = comb & -comb, y = comb + x; // x为独立最低位的1,y为从最低位的1开始连续的1都置为0
    comb = ((comb & ~y) / x >> 1) | y;
}

测试代码

int main() {
    char Set[] = "ABCDEF";
    int N = strlen(Set);
    int K = 4; // 枚举长度为4的所有集合
    int S = (1<<K) - 1;
    while(S < 1<<N) {
        print_set(S, Set);
        int x = S & -S, y = S + x; // x为独立最低位的1,y为从最低位的1开始连续的1都置为0
        S = ((S & ~y) / x >> 1) | y;
    }
}

输出结果

{A,B,C,D}
{A,B,C,E}
{A,B,D,E}
{A,C,D,E}
{B,C,D,E}
{A,B,C,F}
{A,B,D,F}
{A,C,D,F}
{B,C,D,F}
{A,B,E,F}
{A,C,E,F}
{B,C,E,F}
{A,D,E,F}
{B,D,E,F}
{C,D,E,F}