集合的整数表示
做POJ3279的时候,苦于不知道怎么枚举集合,于是看了白书中的专栏《集合的整数表示》小白表示被惊艳到了!
前置知识
- 左移运算符
<<
和右移运算符>>
- 整数的二进制表示
各种操作
用一个整数S表示集合,通过检查S的二进制位数来判断元素有无
此方法可以方便地表示集合(如输出{0, 1, …, n-1}的所有子集,编程较困难,这里只需要for(int S = 0; S < 1 << n; S++
)
如S = 6时,二进制为110,第1个元素无,第二三个元素有
下面是对整数表示集合的各种操作
方法 | 表示 |
---|---|
建立空集 | 0 |
只含有第i个元素的集合 | 1 << i |
含有全部n个元素的集合{0, 1, …, n-1} | (1 << n) - 1 |
判断第i个元素是否属于集合S | if(S >> i & 1) |
向集合中加入第i个元素S∪{i} | S | 1 << i |
从集合中去除第i个元素S\{i} | S & ~ (1 << i) |
集合S和T的并集S∪T | S | T |
集合S和T的交集S∩T | S & T |
枚举集合 | for(int S = 0; S < 1 << n; S++){//对集合的处理} |
枚举某个集合sup的子集
例如枚举01101101这样的集合,要将01100000或00101101等子集没去出来。
此时不能用上面的sub加一枚举集合的方法(for(int S = 0; S < 1 << n; S++
)
因为sub + 1 不一定是sup的子集
而(sub + 1) & sup
虽然是sup的子集,但很有可能依旧是sub。
所以我们要反过来,从sup开始每次-1直到0为止
由于sub-1并不一定是sup的子集
所以我们把它与sup进行按位与
这样可以将sup所有的子集按照降序列举出来
(sub - 1) & sup
会忽略sup中的0而从sub中减去1
代码
1 | int sub = sup; |
枚举{0, 1, …, n - 1}所包含的所有大小为k的子集的方法
按字典序排序,最小的子集是(1 << k) - 1
,所以用它作为初始值
以0101110为例,求出comb的下一个二进制码
- 求出最低位的1开始的连续的1的区间(0101110->0001110)
- 将这一区间全部变为0,并将区间左侧的那个0变为1(0101110->0110000)
- 将第(1)步里取出的区间右移,直到剩下的1的个数减少了1个(0001110->0000011)
- 将第(2)步和第(3)步的结果按位取或(0110000 | 0000011 = 0110011)
x & (-x)
即x & ((~x) + 1)
,是求x最低位的1独立出来后的值,如
x | -x | x & (-x) |
---|---|---|
0001 | 1111 | 0001 |
0010 | 1110 | 0010 |
0011 | 1101 | 0001 |
0100 | 1100 | 0100 |
0101 | 1011 | 0001 |
0110 | 1010 | 0010 |
0111 | 1001 | 0001 |
取出最低位的1后,设它为x
通过计算y = comb + x
就将comb从最低位的1开始的连续的1都置零了
由于在comb中加上x后没有变化的位,在 ~y中全都取相反的值
而最低位1开始的连续区间在~y中依然是1
区间左侧的那个0在~y中也依然是0
于是通过计算z = comb & ~y
就得到了最低位1开始的连续区间(此时完成1)
同时y也是2要求的值(此时完成2)
那么首先将z不断右移,直到最低位为1(计算z / x
即可)
这样将z / x
右移一位就得到了第3步要求的值(此时完成3)
将2和3得到的值按位与就得到了comb下一个二进制列(此时完成4)
因为从n个元素的集合中进行选择,所以comb的值不能大于等于1 << n
循环结束,得到大小为k的所有子集的升序枚举
代码
1 | int comb = (1 << k) - 1; |