一、简介
对于使用状态压缩方法表示的集合A，如何遍历使用位运算遍历集合A的所有子集。
二、代码与注释
0. 符号假设
- 假设全集为
S。 S的元素个数为n。A为集合S的子集。
可以使用状态压缩方法加位运算表示集合A。
例如：S = {a, b, c, d}，A = {a, b, d}，那么可以使用状态1011(2)，即11(10)，表示集合A。
1. 暴力遍历子集
直接遍历全集S的所有子集状态state，并判断state是否为A的子集。
int n = S.size();
for(int state=0; state<(1<<n); state++){
if((state|state_A) == state_A){
cout<<state<<" ";
}
}
2. 位运算遍历子集
另外可以根据状态压缩的特点，使用位运算计算集合A的所有子集。原理不解释，只给出代码。
state = state_A;
do{
cout<<state<<" ";
state = (state-1)&state_A;
}while(state!=state_A);
三、参考引用
[1]. 状态压缩位运算 & 求二进制子集
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
