集合的二进制操作

集合与二进制

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

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

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

举个例子，8 个元素编号依次为 ，那么编号为 的集合可以用 来表示。那么空集 可用 来表示（即都不存在），同理全集可用 表示。

集合的操作

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

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

实例

枚举所有子集

要将集合 的所有子集都枚举出来的话，可以这样：

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

从空集开始，然后按照 的升序顺序枚举出来。

测试代码

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}