C++ 子集生成 Subset Generation

数据结构、算法与应用 C++语言描述

第一章 习题25

子集生成法（Subset Generation）

三元素集{a,b,c}的子集是：{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示，分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。

输出n个元素的所有子集（以01序列的形式）。

在网上看了一下基本上最终输出的都是数组，但并没有按照题目输出01序列。所以我这里严格按照题目来解。

分析

子集生成是一个完全排列组合问题，包括退化情况空集，以及极限情况自身。 其他的情况分别是[1,n)个元素的任意组合。 所以如果递归的话，也就是每一次元素数量+1 或者是-1，如果不是输出01序列，那么输出的元素个数就刚好等于递归中的n。输出序列的时候，只需要在其他位置补0即可。而补0逻辑也可以反过来考虑，即默认是n个0 e.g. 0000，随着循环的i改变，在不同的位置上填1e.g. 0001,0010,0100,1000，这样更加便捷。

至此，已经有了算法的模型了：

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void subsetGeneration( T* const A, int len, string code = "", int focus = 0 ){

    if( focus > len ) return;
    if( focus == len ){ cout << string(len,'1') << endl; return; }
    if( focus == 0 ){ cout << string(len,'0') << endl; }

    if( code == "" ){ code = string(len,'0'); }

    code[focus] = '1';
    for( int i = focus; i<len; i++ ){
        code[i] = '1';
        cout << code << endl;
        code[i] = '0';
    }

    subsetGeneration( A, len, code, focus + 1 );
}
int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

思考1 上述算法已经成功解题，但是思维略显复杂，直觉上就感觉不是一个优质解。

把题目的描述抛开，仔细考虑一下。排列组合特别是此题中的01序列，是不是任意一个元素有2个可能分别是0一次，1一次。 那这样的话，用迭代的方式来做，可以有更好的效率，更清晰的思路。

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

void subsetGeneration( int len ){

    string code( len, '0' );
    cout << code << endl;

    for( int i = 0; i<len; i++ ){
        for( int j = i; j< len; j++ ){
            code[j] = '1';
            cout << code << endl;
            code[j] = '0';
        }
        code[i] = '1';
    }
}

int main(){
    subsetGeneration( 4 );
    return 0;
}

输出：

0000
1000
0100
0010
0001
1100
1010
1001
1110
1101
1111

思考2 既然已经解出了二进制码，那么怎么结合二进制码输出所有的集合呢？

很简单，在进行输出的时候将code[n]显示为原数组中的对应元素。且code中字符串为0则不输出；

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void coutElements( T* const A, int len, string code ){
    cout << '{';
    bool first = true;
    for( int i = 0; i < len; i++ ){
        if( code[i] == '1' ){
            if( !first ){
                cout << ',';
            }else{
                first = false;
            }
            cout << A[i] ;
        }
    }
    cout << '}' << endl;
}

template <typename T>
void subsetGeneration( T* const A, int len ){

    string code( len, '0' );
    cout << "{}" << endl;

    for( int i = 0; i<len; i++ ){
        for( int j = i; j< len; j++ ){
            code[j] = '1';
            coutElements( A, len, code );
            code[j] = '0';
        }
        code[i] = '1';
    }
}

int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

输出：

{}
{a}
{b}
{c}
{d}
{a,b}
{a,c}
{a,d}
{a,b,c}
{a,b,d}
{a,b,c,d}