前言
今天整理以前的竞赛笔记时,发现了当时写的一个模板:
我愣是看了半天,也没想明白当时我想表达什么(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 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
...
(正文完)
后记
发现这个算法人也太优秀了吧!!太巧妙了!
(小白书:挑战程序设计竞赛)