集合 —— 子集

科技前沿 • 2025-03-17 18:39 • 阅读 117

大家好，我是讯享网，很高兴认识大家。

【概述】

在集合论中，子集是一个较常用的概念，当给出一个集合 {0,1,2,...,n-1} 时，常需要生成所有的子集。

生成子集有三种方法：增量构造法、位向量法、二进制法

其中，二进制法除了可以生成子集，还是一种集合的表示方法。

【子集生成算法】

1.增量构造法

每次选出一个元素放到集合中，然后打印当前集合，由于集合 A 中的元素不确定，因此每次递归调用都要输出当前集合，这样一来，递归的边界也不需要显示的确定，当无法继续添加元素时，即停止递归

int A[N]; void subset(int cur,int n){ for(int i=0;i<cur;i++)//打印当前集合 printf("%d ",A[i]); printf("\n"); int num=cur?A[cur-1]+1:0;//确认当前元素最小可能值 for(int i=num;i<n;i++){ A[cur]=i; subset(cur+1,n); } } int main(){ int n; scanf("%d",&n); subset(0,n); return 0; }

讯享网

2.位向量法

位向量法是通过构造一个位向量 B[i]，然后构建解答树，当 B[i]=1 时，说明 i 在子集 A 中

讯享网

讯享网int B[N]; void subset(int cur,int n){ if(cur==n){ for(int i=0;i<cur;i++)//打印当前集合 if(B[i]) printf("%d ",i); printf("\n"); return; } B[cur]=true;//选取当前元素 subset(cur+1,n); B[cur]=false;//不选取当前元素 subset(cur+1,n); } int main(){ int n; scanf("%d",&n); subset(0,n); return 0; }

3.二进制法

二进制法除了用于生成集合子集外，还是一种集合的表示方法。

对于集合 {0,1,2,...,n-1} 的子集，利用二进制来表示：以 1、0 的取值来表示从右向左第 i 位表示元素 i 是否在集合中，因此，可用 STL 中的 bitset<N> 来表示一个从 0~N-1 的集合，关于 bitset：点击这里

由于二进制位运算的特点，当两个子集 A、B 逐位进行位运算 A&B、A|B、A^B 时，分别对应两个集合的交集、并集、对称差集

此外，当全为 0 时，表示空集；当全为 1 时，表示全集，即 allBits=(1<<n)-1，那么，对于集合 A 的补集为：allBits^A

void subset(int cur,int n){ for(int i=0;i<n;i++) if(cur&(1<<i)) printf("%d ",i); printf("\n"); } int main(){ int n; scanf("%d",&n); for(int i=0;i<(1<<n);i++) subset(i,n); return 0; }

【例题】

Subset（POJ-3977）(map+枚举子集)：点击这里