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 }
上一篇: 数据结构 &不带头结点的单链表