powerset

[Gunnar G]

I have a
vector<int> x;
and I would like to
call the function

foo( a_subset_of_x )

for ALL subsets of x (i.e. the powerset of x)

Is this possible in an easy way?

[Karl Heinz Buchegger]

Gunnar G wrote:

I have a
vector<int> x;
and I would like to
call the function

foo( a_subset_of_x )

for ALL subsets of x (i.e. the powerset of x)

Is this possible in an easy way?

Use a recursive function

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> Set;

void PrintSet( int Count, Set& TheSet )
{
cout << Count << ": ";
for( size_t i = 0; i < TheSet.size(); ++i )
cout << TheSet[i] << " ";
cout << endl;
}

void Iterate( int& Count, int StartWith, Set& TheSet, Set& Helper )
{
PrintSet( Count, Helper );
Count++;

for( size_t i = StartWith; i < TheSet.size(); ++i ) {
Helper.push_back( TheSet[i] );
Iterate( Count, i + 1, TheSet, Helper );
Helper.pop_back();
}
}

void Iterate( Set& TheSet )
{
Set Tmp;
int Cnt = 1;
Iterate( Cnt, 0, TheSet, Tmp );
}

int main()
{
Set S;

S.push_back( 1 );
S.push_back( 2 );
S.push_back( 3 );
S.push_back( 5 );
S.push_back( 7 );
S.push_back( 11 );

Iterate( S );

return 0;
}
--
Karl Heinz Buchegger
kb******@gascad.at