异想天开

What's the true meaning of light, Could you tell me why

求集合子集

日期:2015-10-04 15:09:31
  
最后更新日期:2015-10-04 15:33:00
求子集,对于每个元素而言,只有在这个子集或不在这个子集两种可能。而依次对每个元素进行一次选择,就可以求出所有的子集。这里有两种方式,递归的方式,就是二叉树的中序遍历。另外一种方式,就是每个元素映射为一个bit位,那么解空间就是全0到全1的组合。
[code lang="cpp"]
#include<stdio.h>
#include <assert.h>

//求编号为 1 2 3 4 5集合的子集
int subset(int *base, int *size, int n,int total)
{
assert(*size <= n);
int num = *size;
if (total == n)
{
int i = 0;
for (i = 1; i <= num; ++i)
{
printf("%d ",base[i]);
}
if (0 == num)
{
printf("#\n");
}
else
{
printf("\n");
}
return 0;
}

base[num+1] = n + 1;
*size = num + 1;
subset(base,size,n+1,total);
*size = num;
subset(base,size,n+1,total);
return 0;
}

//位图映射方式
int subset1(int n)
{
int total = 1<<n ;
int i = 0;
for (i = 0; i < total; ++i)
{
int j = 0;
for (j = 0; j < n; ++j)
{
if ((1 << j) & i)
{
printf("%d ",j+1);
}
}
printf("\n");
}
return 0;
}

int main(int argc, char *argv[])
{
// int base[6];
// int num=0;
// subset(base,&num,0,5);
subset1(5);
return 0;
}
[/code]