随记 – 四月九日 – 利用二进制数高效枚举集合

以下所有操作均可以通过递归DFS每一位并作相应判断实现。但以下写法实现简洁、常数较小，不失为一种优美的技巧。

下文采用$S_i$表示第$i$个集合，$\text{msk}$表示其二进制表示。

简单集合运算

• 并：$S_1 \cup S_2 \leftarrow \text{msk}_1 \mid \text{msk}_2$
• 交：$S_1 \cap S_2 \leftarrow \text{msk}_1\space\&\space\text{msk}_2$
• 差：$S_1 \setminus S_2 \leftarrow \text{msk}_1\space\&\space(\sim\text{msk}_2)$
• （相对于该二进制数类型最大值的）补集：$\sim\text{msk}$
• 对称差集：$S_1 \Delta S_2 \leftarrow {\text{msk}_1}^{\space\land}\space \text{msk}_2$

子集与超集

• 枚举集合$S$的所有子集。

  考虑二进制数$\text{msk}_0=S$，依次枚举字典序更小的二进制表示。有$\text{msk}’\leftarrow (\text{msk}-1)\space\&\space \text{msk}_0$，即取枚举到的集合与$S$的交，直到$\text{msk}=0$（空集）。显然可以不重不漏地枚举完成所有子集。

  当然，也可以通过lowbit(msk)运算取出集合的所有元素，然后建立$[0, 2^{|S|})$和子集的映射，枚举连续的二进制数即可。

• 枚举集合$S$的所有超集。

  同理，依次枚举字典序更大的集合。有$\text{msk}’\leftarrow (\text{msk}+1)\mid \text{msk}_0$，即取枚举到的集合与$S$的并集。直到超过给定的某个限定值。

• 枚举集合$S$的所有大小为$k$的子集。

  首先通过lowbit(msk)取出$S$中所有元素，建立$[0, 2^{|S|})$对所有子集的映射。

  按照字典序从小到大枚举。具体地，我们以$\text{msk}=2^k-1$作为第一个枚举的集合，然后依次进行以下操作：

  • 记$l=\operatorname{lowbit}(\text{msk})$，$p=\text{msk}+l$。
  • 现在我们得到集合$p$，由于$l$导致了至少一次进位，故$\operatorname{popcount}(p)\leq k$。
  • 考虑找出在$\text{msk}$中，紧挨$l$的所有更高位的二进制位$1$。它们都因进位而变成$0$。因此，有$q=\text{msk}\space\&\space \sim p$表示上述$0 \rightarrow 1$的位。
  • 现在我们将这缺失的若干位补足到$p$的后面，即$\text{msk}’=p+\dfrac{q}{2l}$，也即将这连续的若干位向右移动到最低位，去除最高位$1$，并取它们和$p$的并。

  本质上，如果$l$的二进制表示左侧有$c>0$个连续的$1$，则在字典序表示中，在这$c$位$1$的左侧状态不变的情况下，$\text{msk}$所表示的已经是能够达到的字典序最大的集合。因此，我们被迫移动（进位）第$c$位$1$，在新的状态下，$\text{msk}’$最低位的$c$个$1$就是最小字典序的子集。例如$\text{0b1010}{\color{red}1}{\color{blue}11}{00} \rightarrow \text{0b101}{\color{red}1}{\color{green}000}{00} \rightarrow \text{0b101}{\color{red}1}000{\color{blue}{11}}$。

  1
  2
  3
  4
  5
  6
  for (int msk = (1<<k)-1; msk < (1<<n);) {
  	// 将msk映射回原集合的子集
  	// ...
  	int l = msk & -msk, p = msk + l;
  	msk = ((msk & ~p) / l >> 1) | p;
  }