Given a set of numbers, how do we generate its power set?
For example for the set {1,2} the power set is given below.
{ {}, {1}, {2}, {1,2} }
A power set is nothing but all the possible subsets of a given set. If a set contains N elements, it’s power set contains 2N elements. This is evident from the above example.
Here is how our method works.
All the subsets can be identified by an integer. The binary representation of that integer says which elements from the original set present in that subset.
For example let us consider a set of two elements {1,2}, the power set of this can be represented by four integers
0 = 0000 – Empty subset
1 = 0001 – Fist element is present
2 = 0010 – Second element is present
3 = 0011 – First and Second elements are present
In the following C++ program, the outer loop runs from 0 to 2n where n is the size of the set. For each integer, the inner loop checks for set bit positions and accordingly add those numbers to the current subset.
Since we have to generate all the possible subsets, the complexity of this method is O(2^n).
#include <iostream>
#include <set>
#include <vector>
using namespace std;
//Generates the power set of integers provided in inputSet,
//output in pSet
void generatePowerSet( vector<int> &inputSet, set< set<int> > &pSet )
{
int i = 0;
int n = inputSet.size();
//There will be 2^n subsets; generate them
while ( i < (2 << n) )
{
set<int> subSet;
int j = 0;
int k = i;
while( k&(k-1) ) //Until k contains at-least one set bit
{
//If jth bit is set, add the jth element to the subset
if( k & 1)
{
subSet.insert( inputSet[j] );
}
k = k >> 1;
j++;
}
//Add the subset to the powerset
pSet.insert(subSet);
i++;
}
}
//Utility to print the powerset
void printPowerSet( set< set<int> > &pSet)
{
set< set<int> >::iterator setIter;
set<int>::iterator intIter;
for( setIter = pSet.begin(); setIter != pSet.end(); ++setIter )
{
cout<<"{ ";
for( intIter = setIter->begin(); intIter != setIter->end(); intIter++ )
{
cout<<*intIter<<" ";
}
cout<<"}"<<endl;
}
}
int main()
{
int n; // number of elements
cin>>n;
vector<int> intSet;
int i;
//Read the set elements
for( i = 0; i < n; i++ )
{
int x;
cin>>x;
intSet.push_back(x);
}
set< set<int> > powerSet;
generatePowerSet( intSet, powerSet );
printPowerSet( powerSet );
return 0;
}