前言

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

我愣是看了半天,也没想明白当时我想表达什么(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},全部子集有00000001001000110100010101100111,其中0000代表空集

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

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

我们不难得出,枚举集合{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的子集”的理解-LMLPHP

如何枚举?

为了将所有情况枚举出来,我们可以枚举集合{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 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 00101101 01001101 10001110 00011110 00101110 01001110 10001111 0000...

(正文完)

后记

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

(小白书:挑战程序设计竞赛)

参考文献

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

XDU_Skyline.集合的表示及其运算

05-26 10:34