关于“枚举{0,1,…,n-1}所包含的所有大小为k的子集”的理解

前言

今天整理以前的竞赛笔记时，发现了当时写的一个模板：

枚举{0,1,…,n-1}所包含的所有大小为k的子集：

int comb = (1 << k) - 1;
while (comb < 1 << n) {
	//进行针对组合的处理 
	int x = comb & -comb, y = comb + x;
	comb = ((comb&~y) / x >> 1) | y;
}

我愣是看了半天，也没想明白当时我想表达什么(lll￢ω￢)

然后就百度了一下，结合一些描述，终于想起来这貌似是从小白书上扒下来的

话说我小白书已经失踪一年了，到现在还没找到......

以防以后又把它忘了，特此记录

什么是“枚举{0,1,…,n-1}所包含的所有大小为k的子集”

“枚举{0,1,…,n-1}所包含的所有大小为k的子集”与二进制状态压缩关系密切，其本质为利用二进制与位元算表示和操作集合，举个例子：

含有n个元素的集合{0,1,…,n-1}，就有n个二进制位，第i个二进制位代表第i个元素，第i个二进制位为1代表第i个元素存在于集合，第i位二进制位为0代表第i个元素不存在于集合。（i<=n）

含有3个元素的集合{0,1,2}，全部子集有0000、0001、0010、0011、0100、0101、0110、0111，其中0000代表空集∅。

二进制数与集合对应关系如下：

我们不难得出，枚举集合{0,1,…,n-1}的所有子集的方法：

for (int S = 0; S < 1 << n; S++) {
	//对子集的操作 
}

S < 1 << n等同于S <= ( (1<<n)-1 ),(1<<n)-1为含有n个元素的集合{0,1,…,n-1}。

解决“枚举{0,1,…,n-1}所包含的所有大小为k的子集”，我们只需弄清什么是“大小为k的子集”。

“大小为k的子集”就是有k个元素的子集，也就是二进制中有k个1。

含有3个元素的集合{0,1,2}所包含的所有大小为2的子集：

如何枚举？

为了将所有情况枚举出来，我们可以枚举集合{0,1,…,n-1}的所有子集，在枚举时加入判断，判断当前子集是否满足“大小为k的子集”。

从实现上来看，这是可行的：

int n, k;
int getsum(int S) {// 统计二进制中1的个数
	int ans = 0;
	while (S){
		if (S & 1)
			ans++;
		S >>= 1;
	}
	return ans;
}
for (int S = 0; S < 1 << n; S++) {
	if (getsum(S) == k) {
		// 对子集的操作
	}
}

但这不够优秀，不如说相当低效，这时我们需要找到一种更优秀的枚举方法。

白书上提供了一种思路：

int comb = (1 << k) - 1;
while (comb < 1 << n) {
	//进行针对组合的处理 
	int x = comb & -comb, y = comb + x;
	comb = ((comb&~y) / x >> 1) | y;
}

comb是按字典序排列的最小子集，在while循环中，comb会一直增大，直到找完所有大小为k的子集。

我们利用刚刚的例子，来模拟算法找“含有3个元素的集合{0,1,2}所包含的所有大小为2的子集”的过程：

（此例中 k=2，n=3）

第一次循环，我们找到了按字典序排列的最小子集，也就是comb的初始值0011，之后comb“按算法提供方法”增大，comb的值变为0101。

第二次循环，我们找到的是0101，之后comb“按算法提供方法”增大，comb的值变为0110。

第三次循环，我们找到的是0110，之后comb“按算法提供方法”增大，comb的值变为1001。

此时，comb的值不满足“comb < 1<<n”即不满足"1001 < 1000"，算法结束于第四次循环的开始。

“按算法提供方法”也就是每次求下一个子集的方法如下：

（以1100 1100到其下一个子集1101 0001为例）

int comb = (1 << k) - 1;
while (comb < 1 << n) {
	//进行针对组合的处理 
	int x = comb & -comb, y = comb + x;
	comb = ((comb&~y) / x >> 1) | y;
}

我们将核心代码提取并拆解：

    int x = comb & -comb; //步骤(2)
    int y = comb + x;	  //步骤(3)
    int z = comb & ~y;	  //步骤(1)
    int b = (z / x) >> 1; //步骤(4)，'z/x'相当于去掉右侧多余的0，'>>1'则使剩下的1的个数减少一个
    comb = b | y;	  //步骤(5)

（1）取出字典序最小的1的连续区间，1100 1100 → 0000 1100

（2）找到字典序最小的1的位置，1100 1100 → 0000 0100

（3）将字典序最小的1的连续区间置为0，并将区间左侧第一个0置为1，1100 1100 → 1101 0000

（4）将 (1) 取出的区间右移，直至区间中1的个数减少一个，0000 1100 → 0000 0001

（5）将 (4) 的结果与 (3) 的结果取并集，0000 0001 | 1101 0000 → 1101 0001

按照这种方法，我们不难找出后续的子集：

1101 0010、1101 0100、1101 1000、1110 0001、1110 0010、1110 0100、1110 1000、1111 0000...

（正文完）

后记

发现这个算法人也太优秀了吧！！太巧妙了！

（小白书：挑战程序设计竞赛）

参考文献

weixin_30443075.集合的整数表示与子集枚举

XDU_Skyline.集合的表示及其运算