子集生成方法

问题

输出n个元素的所有子集，如{a,b,c}的子集为{}，{a}，{b}，{c}，{a,b}，{a,c}，{b,c}，{a,b,c}

解决

二进制法

如果这些子集用0/1表示的话，那么上面的子集可表示为000，001，010，100，110，101，011，111，其中1表示这个元素属于这个子集，0表示不属于。

这种0/1表示法让我想到了数据在内存中的存放也是0/1，所以下面用这种思路解决这个问题。

#include <iostream>
#include <cstring>
using namespace std;
void SubsetGeneration(const char *s)
{
    unsigned long long n = 1;
    int len = strlen(s);
    n <<= len;//n = 2^len
    for(unsigned long long i = 0;i < n;++i)//i的二进制数表示s每一位的状态，最后一位与s[0]对应，倒数第二位与s[1]对应
    {
        unsigned long long cmp = 1;//cmp的二进制表示只有一个1，其他都是0，用来判断s每一位的状态
        for(int j = 0;j < len;++j)
        {
            if(i & cmp)//利用按位与来判断
                cout << s[j];
            cmp <<= 1;//将1往后移动一位
        }
        cout << endl;
    }
}
int main()
{
    char a[sizeof(long long)+1];
    while(cin >> a)
    {
        SubsetGeneration(a);
    } 
    return 0;
}

这种方法虽然运算效率快，但法无法解决元素数大于sizeof(long long)，因此我们可以利用一个bool的数组来表示每一位的状态，下面给出改良的算法

位向量法

#include <iostream>
#include <cstring>
using namespace std;
void BitVector(char *s,bool *bit,int begin,int end)
{
    if(begin == end){
        for(int i = 0;i < end;++i)
            if(bit[i])
                cout << s[i];
        cout << endl;
        return;
    }
    bit[begin] = false;
    BitVector(s,bit,begin + 1,end);
    bit[begin] = true;
    BitVector(s,bit,begin + 1,end);
}
int main()
{
    char s[10];
    while(cin >>s)
    {
        int n = strlen(s);
        bool *bit = new bool[n];
        BitVector(s,bit,0,n);
        delete[] bit;
    }
    return 0;
}

增量构造法

#include <iostream>
using namespace std;
int a[20];
/*递归输出n以内所有的子集,其中cur为当前下标,初始值0*/
void print_subset(int n,int* a,int cur)
{
	for (int i=0; i<cur; i++) //每次递归输出当前子集,靠它来最后输出上一层指定的子集
		cout<<a[i]<<' ';
	cout<<endl;//以行分隔
//找到当前子集首个值,因为按字典顺序输出，所以每次找到最小的元素，cur>0则minElem=a[cur-1]+1,否则为0
	int minElem = cur?a[cur-1]+1:0;
//从子集第一个值开始遍历,先不看下面的print_subset(n,a,cur+1);但看这for循环，
//可知是将子集第一个值从头往后依次赋值为minElem-n-1.每次第一个值变化后递归设置下一个值(相当于下一层的第一个值)
	for (int i=minElem; i<n; i++)
	{
		a[cur]=i;//当前层子集第一个值
//cur+1表示当前层值设置完毕，开始递归下一层，和前面步骤一样。
//到达最后一层结束后return 到上一层，然后i++,a[cur]的值(首元素)改变，又反复递归下一层...
		print_subset(n,a,cur+1);
	}
}
int main()
{
	int n ;
	while (cin>>n,n)
        print_subset(n,a,0);
    return 0;
}