大家好，又见面了，我是全栈君。
如果我们有一个求集合的所有子集(包括集合自身)的需求，即有一个集合s,包括两个元素 <a,b>，则其所有的子集为<a,ab,b>.
不难求得，子集个数sn与原集合元素个数n之间的关系为：sn=2^n-1。
本文分别讲述两种实现方法：
一：位图法：
1）构造一个和集合一样大小的数组A，分别与集合中的某个元素相应，数组A中的元素仅仅有两种状态：“1”和“0”，分别代表每次子集输出中集合中相应元素是否要输出。这样数组A能够看作是原集合的一个标记位图。
2）数组A模拟整数“加一”的操作，每“加一”之后，就将原集合中全部与数组A中值为“1”的相相应的元素输出。
设原集合为<a,b,c,d>。数组A的某次“加一”后的状态为[1,0,1,1]，则本次输出的子集为<a,c,d>。
详细代码例如以下：
/*使用非递归的思想 假设有一个数组 大小为n
那么就使用n 位的二进制 假设对应的位为1 那么就输出这个位
假设对应的位为0 那么就不输出这个位*/
/*
使用位图的思想 构造一个位集合 大小和数组大小一样，假设位图中对应的
位为1,表示能够输出这个数组中的元素 假设位图中对应位为0 表示数组中对应位不输出
这里模拟位图使用的数组 ，这里的重点是模拟数组加1的操作
*/
/*使用数组模拟位图加1的操作 数组能够一直加1 直到数组内全部元素都是1
函数返回值为bool 数组初始化最高位为1*/
#define MAX_LEN 10
void bitmap(char str[],const int n)
{
bitset<MAX_LEN> count;
wang.set();
int i=0;
unsigned long value = wang.to_ulong();
cout<<wang<<" "<<value<<endl;
int count=0;
while(value)
{
bitset<MAX_LEN> bit(value--);
for(i=0;i<bit.size();i++)
if(bit[i])
cout<<str[i];
cout<<endl;
count++;
}
cout<<count<<endl;
}
3）时间复杂度：O(n*2^n)。事实上，在遍历输出子集的过程中。能够对程序做进一步的优化。
比如。在第m次迭代中。仅仅须要遍历前k个元素，k=log2(m)+1。这样，不考虑数组模拟”加一”操作的话,总遍历次数为Sn=(n-2)*2^n+2,n>=2;Sn=1,n=1。尽管复杂度不变，但总执行时间会降低。
4）空间复杂度：该方法每次迭代都是独立进行，与上次迭代的结果没有不论什么关系。因此每次输出子集之后内存都能够被反复利用。
仅仅须要一个与原集合相同大小的数组。空间复杂度为O(n)。
二：递归迭代法：
1）採用递归迭代。详细步骤例如以下，
设。原始集合s=<a,b,c,d>，子集结果为r：
第一次迭代：
r=<a>
第二次迭代：
r=<a ab b>
第三次迭代：
r=<a ab b ac abc bc c>
第四次迭代：
r=<a ab b ac abc bc c ad abd bd acd abcd bcd cd d>
每次迭代，都是上一次迭代的结果+上次迭代结果中每一个元素都加上当前迭代的元素+当前迭代的元素。
详细代码例如以下：
/*上述方法不可用 明确递归的思想 以下每次都是输出back中的字符就可以
这次输出的子集就是上次输出的子集 +这次迭代的元素 + 这次迭代的元素的本身*/
#if 1
void print(char* str)
{
/*使用两个数组。一个记录上次迭代的结果
一个记录这次须要输出的结果
vec记录的是下次迭代须要參考的子集
back记录的是參考vec迭代以后生成新的子集
*/
int count=0;
vector<char> vec;
vector<char> back;
int j;
for(int i=0;i<strlen(str);i++)
{
if(i == 0)
{
vec.push_back(str[i]);
vec.push_back(',');
back=vec;
}
else
{
for(j=0;j<back.size();j++)
if(back[j] == ',')
{
back.insert(back.begin() +j,str[i]);
j++;
}
back.push_back(str[i]);
back.push_back(',');
}
for(j=0;j<back.size();j++)
{
if(back[j] == ',')
{
printf("\r\n");
count++;
}
else
printf("%c",back[j]);
if(i)
vec.push_back(back[j]);
}
back=vec;
}
printf("sub_set count is %d \r\n",count);
}
#endif
2）时间复杂度
依据上述过程，不难求的。第k次迭代的迭代次数为：2^k-1。
n>=k>=1。迭代n次，总的遍历次数为：2^(n+1)-(2+n),n>=1。
则时间复杂都为O(2^n)。
3）空间复杂度
因为该算法。下一次迭代过程都须要上一次迭代的结果，而最后一次迭代之后就没有下一次了。
因此如果原始集合有n个元素。则在迭代过程中，总共须要保存的子集个数为2^(n-1)-1,n>=1。
但须要注意的是，这里之考虑了子集的个数，每一个子集元素的长度都视为1，这点要注意。
总结：
递归是非常耗时的。由于是递归，在第一种方法时，使用了C++中的bitset,这种方法效率非常高，在第二个方法中，使用两个向量的目的是，一个向量记录了这次迭代须要输出的集合，一个向量是为了这次迭代须要參考上次输出的情况。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115429.html原文链接：https://javaforall.net
