欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++ : 二进制法生成子集

程序员文章站 2024-03-21 14:44:46
...

    一个有 n 个元素的集合 (n >=0,n为整数),可以生成 2^n个子集。例如 {a,b} 可以生成4个子集    {空}、{a},{b}{a,b}

二进制法就是 从0到 2^n用二进制表示,为1的对应的数组位置元素 纳入子集集合。

例如   a = {a,b,c,d}  有 16 个子集,建立如下表

十进制数 二进制数 1对应的数组元素 结果集
0 0000  
1 0001 a[3] d
2 0010 a[2] c
3 0011 a[2], a[3] c,d
4 0100 a[1] b
5 0101 a[1],a[3] b,d
6 0110 a[1],a[2] b,c
7 0111 a[1],a[2],a[3] b,c,d
8 1000 a[0] a
9 1001 a[0],a[3] a,d
10 1010 a[0],a[2] a,c
11 1011 a[0],a[2],a[3] a,c,d
12 1100 a[0],a[1] a,b
13 1101 a[0],a[1],a[3] a,b,d
14 1110 a[0],a[1],a[2] a,b,c
15 1111 a[0],a[1],a[2],a[3] a,b,c,d

 

 

 /**
         * <p> 获取所有子集
         * @tparam ElemType  返回值类型
         * @tparam _InputIterator 线性表的迭代器类型
         * @param _first1      线性表的起始地址
         * @param _last1    线性表的结束地址
         * @param _null     用变量来指定返回值类型避免编译不过
         * @return  所有子集
         */
        template<class ElemType,class  _InputIterator>
        vector<vector<ElemType>> makeSubset(_InputIterator _first1, _InputIterator _last1, ElemType _null ){
            int n = _last1 - _first1;
            vector<vector<ElemType>> ret;
            // 2的n次方   1<<n
            for(int s=0;s<(1<<n);s++) {
                vector<ElemType> subRet;
                for (int i = 0; i < n; i++) {
                    if (s & (1 << i)) //1左移i位,监测s的哪一位为1,为1的话输出
                    {
                        subRet.push_back(*(_first1 + i));
//                        std::cout<<i;
                    }
                }
                ret.push_back(subRet);
//                std::cout << std::endl;
            }
            return  ret;
        }

调用示例:

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
   string aaaa[3]={"7a8","2b2","3c1"};
    string string1;
    vector<vector<string>>aaRet= makeSubset(aaaa, aaaa + 3, string1);
    for (int j = 0; j < aaRet.size(); ++j) {
        cout<<"{";
        for (int i = 0; i < aaRet[j].size(); ++i) {
            cout<< aaRet[j][i] <<" ";
        }
        cout<<"}\n";
    }

}

 

{}
{7a8 }
{2b2 }
{7a8 2b2 }
{3c1 }
{7a8 3c1 }
{2b2 3c1 }
{7a8 2b2 3c1 }