集合的整数表示

做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
2
3
4
5
6
7
int sub = sup;
do
{
//对子集的处理
sub = (sub - 1) & sup;
}
while(sub != sup); //处理完0之后,会有-1 & sup = sup

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

按字典序排序,最小的子集是(1 << k) - 1,所以用它作为初始值

以0101110为例,求出comb的下一个二进制码

  1. 求出最低位的1开始的连续的1的区间(0101110->0001110)
  2. 将这一区间全部变为0,并将区间左侧的那个0变为1(0101110->0110000)
  3. 将第(1)步里取出的区间右移,直到剩下的1的个数减少了1个(0001110->0000011)
  4. 将第(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
2
3
4
5
6
7
8
int comb = (1 << k) - 1;
while(comb < 1 << n)
{
//这里进行针对组合的处理
int x = comb & -comb;
y = comb + x;
comb = ((comb & ~y) / x >> 1) | y;
}
0%