当集合的元素数比较少的时候,我们可以使用整数来表示集合(用到整数的二进制)

一些集合运算可以这么写:

  • 空集:0
  • 只含有第i个元素的集合{i}: 1<<i
  • 含有全部n个元素的集合{0, 1, …, n-1}: (1<<n)-1
  • 判断第i个元素是否属于集合S: if(S>>i&1)
  • 向集合中加入第i个元素:S|(1<<i)
  • 从集合中去除第i个元素:S&~(1<<i)
  • 集合S和T的并集:S|T
  • 集合S和T的交集:S&T

枚举集合S的所有子集

for( int S = 0; S < (1<<n); ++S)
{
     //对于集合的处理
}

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

下面的代码根据字典序升序,枚举出所有满足条件的二进制码

int comb = (1<<k) - 1;
while(comb < (1<<n) )
{
    //这里进行针对组合的处理

    int x = comb & -comb;
    int y = comb + x;
    comb = (((comb & ~y) / x) >>1 ) | y;
}

转载请注明来源:https://www.longjin666.top/?p=1194

你也可能喜欢

发表评论