[经典算法] 排列组合-N元素集合的所有子集(一)

题目说明：

给定一组数字或符号，产生所有可能的集合（包括空集合），例如给定1 2 3，则可能的集合为：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。

题目解析：

如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例如：

000	{}
001	{3}
010	{2}
011	{2,3}
100	{1}
101	{1,3}
110	{1,2}
111	{1,2,3}

了解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned型别加上&位元运算来产生；

如果是32个以内的元素集合可以采用unsigned int来储存，这样直接遍历再根据比特位显示出元素就可以了。

比如3个元素，则对应最大值是2^3 = 8;

for (int i=0; i < 8; i++)

     ShowResult(&i, 3); //根据bit位显示结果

这里我假定任意个元素集合求子集合，通过数组来表示任意长位数；

程序代码：

#include <gtest/gtest.h>

using namespace std;

void ShowResult(bool Bits[], int nSize)

{

    cout << "{";

    for (int i=0; i<nSize; ++i)

    {

        if (Bits[i])

        {

            cout << i+1 << " ";

        }

    }

    cout << "}\n";

}

bool Add(bool Bits[], int nSize)

{

    for (int i = nSize -1; i >= 0; --i)

    {

        Bits[i] = !Bits[i];    // 如果是1变成0再进位，如果是0变成1退出。

        if (Bits[i])

        {

            return true;

        }

    }

    return false;

}

// 二进制法

int GenerateSubset(int nSize)

{

    if (nSize==0)

    {

        cout << "{}" << endl;

        return 1;

    }

    int nCount = 0;

    bool *Bits = new bool[nSize];

    memset(Bits, false, sizeof(bool)*nSize);

    do

    {

        ShowResult(Bits, nSize);

        nCount++;

    }

    while(Add(Bits, nSize));

    delete[] Bits;

    return nCount;

}

TEST(Algo, tCombination)

{

    // 0个数子集合数 =〉2^0 = 1

    ASSERT_EQ(GenerateSubset(0), 1);

    // 3个数子集合数 =〉2^3 = 8

    ASSERT_EQ(GenerateSubset(3), 8);

    // 5个数子集合数 =〉2^5 = 32

    ASSERT_EQ(GenerateSubset(5), 32);

    // 10个数子集合数 =〉2^10 = 1024

    ASSERT_EQ(GenerateSubset(10), 1024);

}

参考引用：

根据组合数和二项式定理

子集个数：Cn0+Cn1+Cn2+...+Cnn = (1+1)^n=2^n

  看书、学习、写代码

巴特西

[经典算法] 排列组合-N元素集合的所有子集(一)

题目说明：

题目解析：

程序代码：

参考引用：

最新文章

热门文章