打印

输出含有N个元素集合的所有子集的算法!

[复制链接]
1818|2
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
乌月明星稀|  楼主 | 2013-10-20 09:29 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
方法一:位沉降
比如 A{ a,b,c}的所有子集输出为:
{a} {b} {c}
{a,b} {b,c} {a,c}
{a,b,c}
之前想到用位沉降的方法,就是用32位长的unsigned long数组,每位都映射一个集合元素,1和0表示被选中和未被选中。
一开始假申请一个数组大小为N/32+1的内存块并清零。
1、对第k个位进行置一(k一开始为0,然后逐次递增);
2、位滚动,位K开始滚动到K+1,在滚动前,先判断K+1上是否已经被选中,如果已经被选中,说明已经沉底,结束本轮操作。
3、将底部所有沉降的元素滚回到头部,对k+1个位进行置一开始滚动k+1的元素。
4、当k+1的元素沉底后,第k个元素滚动到第k+1上,然后沉底的元素滚回k+2上,不断进行滚动循环。

用位表示如下,假设为8位
1、 第一次加入新元素 0000 0001
2、将新元素进行沉底操作,被操作一次都输出一个序列,滚动到尾部为1000 0000
3、重新将新的元素滚回头部为0000 0001 ,对k+1的元素置1为0000 0011
4、继续沉降,先沉降k+1的元素,有1000 0001,底部滚回到k+2的位置0000 0101,并对k的元素滚动到k+1的位置0000 0110
如此通过不断加入新的元素和滚动实现组合的输出。
方法优劣说明:操作复杂,实现麻烦

方法二、字典法
求解析。
能不能介绍一下其他的算法,简单点的

相关帖子

沙发
linfeng24| | 2013-10-20 10:54 | 只看该作者

使用特权

评论回复
板凳
乌月明星稀|  楼主 | 2013-10-20 22:18 | 只看该作者
linfeng24 发表于 2013-10-20 10:54
递归法,具体程序参考http://hi.baidu.com/hightch/item/f89f53d497643c1fd68ed01d

我刚刚写了一个:
/*===================================================================
=团队名称:IMA
=
=作者名称:飞哥
=
=工作单位:广东工业大学智能模型协会
=
=编写日期:2013年10月20日22:10
=
=完成日期:2013年22月20日22:14分
=
=修改人:
=
=修改日期:
=
=版本号  :Version1.0
=
=模块说明:此文件只是用于简单的N元素的所有子集输出,其中N<32,测试通过
=
=====================================================================*/
#include "stdio.h"
const unsigned long Map[]={
        0x00000001,0x00000003,0x00000007,0x0000000f,//位图掩码
        0x0000001f,0x0000003f,0x0000007f,0x000000ff,
        0x000001ff,0x000003ff,0x000007ff,0x00000fff,
        0x00001fff,0x00003fff,0x00007fff,0x0000ffff,
        0x0001ffff,0x0003ffff,0x0007ffff,0x000fffff,
        0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
        0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,
        0x1fffffff,0x3fffffff,0x7fffffff,0xffffffff};
/*函数声明*/
void show(unsigned long T,char N);
/*================================================================================
=函数名称:void main()
=
=传入参数:无
=                  
=返回参数:无
=
=函数说明:main函数
=
=================================================================================*/
void main()
{
        unsigned long num=1;
        char N;
        printf("请输入要测试的元素个数:\t");
        scanf("%d",&N);
        for(;num<Map[N];num++)
        {
                show(num,N);
                }//for
}//main
/*================================================================================
=函数名称:void show(unsigned long T,char N)
=
=传入参数:T:位测试,N:位长度
=                  
=返回参数:无
=
=函数说明:用于显示子集
=
=================================================================================*/
void show(unsigned long T,char N)
{
        char i=0;
        for(;i<=N;i++)
        {
                if(T&0x1)
                {
                        printf("%c",'a'+i);
                }//if
                T=T>>1;
        }//for
        printf("\t");
}//show

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

14

主题

127

帖子

1

粉丝