暴力求解-子集生成_辣条不爱辣的博客-程序员秘密

技术标签：算法

本篇介绍子集生成算法：给定一个集合，枚举所有可能的子集。为了简单起见，本节讨论的集合汇总没有重复元素。

输入：整数n。

输出：对于集合{0,1，.....n-1}，枚举所有可能的子集。

运行结果：

增量构造法。

第一种思路是一次选出一个元素放到集合中。

void print_subset_add(int n,int *A,int cnt)
{
    //增量构造法
    //每次都选一个元素放入集合中
    int i;
    for(i=0;i<cnt;i++) //打印当前集合
        printf("%d ",A[i]);
    printf("\n");
    int s=cnt?A[cnt-1]+1:0; //确定当期集合的最小值
    for(i=s;i<n;i++)
    {
        A[cnt]=i;
        print_subset_add(n,A,cnt+1); //递归构造子集
    }
}

和前面不同，由于A中的元素个数不确定，每次递归调用都要输出当前集合。另外，递归边界也不需要显示确定-如果无法继续添加元素，自然就不会再递归了。

上面的代码用到了定序的技巧：规定集合A中所有元素的编号从小到大排列，就不会把集合{1,2}按照{1,2}和{2,1}输出两次了。

在枚举子集的增量法宏中，需要使用定序的技巧，避免同一个集合枚举两次。

位向量法。

第二种思路是构造一个位向量B[i]，而不是直接构造子集A本身，其中B[i]=1，当且仅当i在子集A中，递归实现如下：

void print_subset_B(int n,int *B,int cnt)
{
    //位向量法
    //构造一个位向量B[i] 而不是直接构造子集A本身，其中B[i]=1当且仅当i在
    //子集A中
    if(cnt==n)
    {
        for(int i=0;i<cnt;i++) //打印当前集合
            if(B[i])
                printf("%d ",i);
        printf("\n");
    }
    else
    {
        B[cnt]=1;
        print_subset_B(n,B,cnt+1);
        B[cnt]=0;
        print_subset_B(n,B,cnt+1);
    }
}

必须当所有元素是否选择全部确定完毕后才是一个完整的子集，因此仍然像以前那样当 if(cur ==n )成立时才输出。

二进制法。

另外，还可以用二进制来表示{0,1,2，....,n-1}的子集S：从右往左第i位（各位从0开始编号）表示元素i是否在集合S中。

为了处理方便，最右边的位总是对应元素9，而不是元素1.

可以用二进制表示子集，其中从右往左第i位（从0开始编号）表示元素i是否在集合中（1表示“在”，0表示“不在”）

此时仅表示出集合是不够的，还需要对集合进行操作。幸运的是，常见的集合运算都可以用位运算符简单实现。

当用二进制表示子集时，位运算中的按位与，或，异或对应集合的交、并和对称差。

这样，不难用下面的程序输出子集S对应的各个元素：

void print_subset_binary(int n,int s)
{
    //二进制法
    for(int i=0;i<n;i++) //打印子集S
        if(s&(1<<i))
           printf("%d ",i);
    printf("\n");
}

而枚举子集和枚举整数一样简单：

for(int i=0;i<(1<<n);i++) //枚举各子集对应的编码0,1,....2^n-1;
    print_subset_binary(n,i);

从代码量看，枚举子集的最简单方法是二进制法。

本文链接：https://blog.csdn.net/baidu_38304645/article/details/83588124

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

使用媒体查询在屏幕宽度改变的时候实时更改样式_LPLIFE的博客-程序员秘密

媒体查询需要一层层查找下去修改，否则无效当屏幕宽度小于1024的时候，.time-box里头的.data内容被隐藏 &lt;li class="time-box"&gt; &lt;div class="time"&gt;{{systemTime}}&lt;/div&gt; &lt;div class="date"&

web前端学习83-86（CSS引入方式---内部样式表，行内样式表，外部样式表）_都取样式表时,内部,行内、链接三种方法插入的不同web_向long.js学习的博客-程序员秘密

文章目录5 CSS 引入方式5.1 CSS的三种样式表5.2 内部样式表5.3 行内样式表5.4 外部样式表5.5 CSS引入方式总结5 CSS 引入方式5.1 CSS的三种样式表前面例子在写CSS时都是写在style中，但是并不是都写在里面的按照CSS样式书写的位置（或者引入的方式），CSS样式表可以分为三大类：行内样式表(行内式)内部样式表(嵌入式)外部样式表(链接式)5.2 内部样式表内部样式表(内嵌样式表)是写到html页面内部。是将所有的CSS代码抽取出来,单独放到一个*

Windows、Linux、ARM、Android、iOS全平台支持的RTMP推流组件EasyRTMP- iOS进入预览界面系统直接崩溃的原因分析_EasyNVR的博客-程序员秘密

EasyRTMP是一套调用简单、功能完善、运行高效稳定的RTMP推流功能组件，支持RTMP推送断线重连、环形缓冲、智能丢帧、网络事件回调，支持Windows、Linux、ARM、Android、iOS平台，支持市面上绝大部分的RTMP流媒体服务器，能够完美应用于各种行业的直播需求，手机直播、桌面直播、摄像机直播、课堂直播等方面。EasyRTMP推流功能特点- 调用简单无论是个...

内网渗透测试：域内权限维持思路总结_域环境设置进程的运行权限_zhang三的博客-程序员秘密

我的Freebuf：https://www.freebuf.com/author/MrAnonymous我的博客：https://whoamianony.top/文章目录Windows 操作系统常见持久性后门Windows系统隐藏账户Shift 粘滞键后门（1）手动制作（2）Empire 下的利用注册表键后门（1）手动制作（2）Metasploit 下的利用（3）Empire 下的利用Windows 计划任务后门（1）利用 at 命令（2）利用 schtasks 命令（3）利用SharPersist工.

可视化 nlp_使用nlp可视化尤利西斯_柠檬大饭饭的博客-程序员秘密

可视化 nlpMy data science experience has, thus far, been focused on natural language processing (NLP), and the following post is neither the first nor last which will include the novel Ulysses, by James ...

java速查手册.chm下载_C语言函数速查手册_吃土皮皮虎的博客-程序员秘密

本手册为chm格式，查询C语言常用函数非常方便字符串函数bcmp,bcopy,bzero,memccpy,memchr,memcmp,memcpy,memicmp,memmove,memset,movmem,setmem,stpcpy,strcat,strchr,strcmp,strcmpi,strcpy,strcspn,strdup,stricmp,strlen,strlwr,strncat,s...