Generate All Subsets

G

Gaijinco

I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
using namespace std;
#include <cmath>

int main(){

const int SIZE=3;
int set[SIZE]={1,2,5};

cout << "For the set { 1 2 5 } all possible sub sets are:" << endl;

for(int i=pow(SIZE,2)-1; i>=0; --i){
int index=2;
int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}
cout << "}" << endl;
}

system("pause");
return 0;
}

However it seems bulky to me. There is another way?

Thank you!
 
A

Alf P. Steinbach

* Gaijinco:
I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
using namespace std;
#include <cmath>

int main(){

const int SIZE=3;

Style: it's a good idea to reserve all uppercase naming for macros.

Coding: it's an even better idea to compute the size from the array instead of
having a constant that can easily get out of synch. Let the compiler count
the items. Computer programs, such as compilers, are very good at counting.

int set[SIZE]={1,2,5};

Consider using a std::set. Just a suggestion.
cout << "For the set { 1 2 5 } all possible sub sets are:" << endl;

for(int i=pow(SIZE,2)-1; i>=0; --i){

You can use the shift left operator "<<" instead of the more general and
inefficient pow function. With pow you may or may not run the risk of
rounding error, giving a result off by one. I haven't checked whether that's
the case or not, but it's not necessary to check that if you use "<<".

Style: counting up is generally preferable to counting down. For example,
it's more robust against a change from signed to unsigned counter variable.
Also it's easier to understand, in most cases.

Otherwise the basic idea of your loop is the usual way of generating subsets,
and I don't think there's any easier way to do it.

int index=2;

Here you mean

int index = SIZE - 1;

int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}

An easier way to do the same:

for( int j = 0; j < SIZE; ++j )
{
if( (i & (1 << j)) != 0 ) { cout << set[index] << " "; }
}

which you can leave to the compiler to optimize (actually the cout call is so
expensive that it dwarfes any optimization of the loop, so an optimization at
the source level would only have a cost, less clear code, and no benefit).

cout << "}" << endl;
}

system("pause");

Not portable... ;-)
return 0;
}

However it seems bulky to me. There is another way?

See above.
 
B

Bob Hairgrove

Style: it's a good idea to reserve all uppercase naming for macros.

Yes indeed ... for example, SIZE is a struct defined by the Windows
API. Not a good idea for one of your own names if you plan on porting
your code to that platform.

Lower-case "size", OTOH, should be OK.
 
J

John Harrison

Gaijinco said:
I been thinking about this topic for a long time. The best I have done
is the following code:

Well there is the recursive variation

#include <iostream>
using namespace std;

void generate_subsets(const int* set, int size, bool* work,
int depth = 0)
{
if (depth == size)
{
cout << "{ ";
for (int i = 0; i < size; ++i)
if (work)
cout << set << ' ';
cout << "}\n";
}
else
{
work[depth] = true;
generate_subsets(set, size, work, depth + 1);
work[depth] = false;
generate_subsets(set, size, work, depth + 1);
}
}

int main()
{
int set[]={1,2,5};
const int set_size = sizeof set/sizeof set[0];
bool work[set_size];
generate_subsets(set, set_size, work);
}

This has the advantage that the size of set it can handle it not limited
by the size of an int.

john
 
G

Gaijinco

I use SIZE because Deitel/Deitel uses it. I know macros are usually in
uppercase, so I suppose that I can use a little hungarian notation and
write kSize, but your idea of letting the compiler count the size of
the array is even better!

I don't know anything about std::set, mind to tell me a little about
it?

I also found this code hard to understand (and it doesn't seem to work
as I copy/paste it) What's the idea behind it?

for( int j = 0; j < SIZE; ++j )
{
if( (i & (1 << j)) != 0 ) { cout << set[index] << " "; }
}

Thanks.
 
K

Kai-Uwe Bux

Gaijinco said:
I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
using namespace std;
#include <cmath>

int main(){

const int SIZE=3;
int set[SIZE]={1,2,5};

cout << "For the set { 1 2 5 } all possible sub sets are:" << endl;

for(int i=pow(SIZE,2)-1; i>=0; --i){
int index=2;
int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}
cout << "}" << endl;
}

system("pause");
return 0;
}

However it seems bulky to me. There is another way?

I use something like this:

template < typename SetType, typename SortedRange >
bool next_subset ( SetType & subset,
SortedRange const & set ) {
for ( typename SortedRange::const_iterator iter = set.begin();
iter != set.end(); ++ iter ) {
if ( subset.empty() ) {
subset.insert( *iter );
return( true );
} else if ( *iter != *subset.begin() ) {
subset.insert( *iter );
return( true );
} else {
subset.erase( subset.begin() );
}
}
return( false );
}


#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <vector>

int main ( void ) {
std::vector< int > i_vect;
for ( int i = 0; i<5; ++i ) {
i_vect.push_back( i );
}
std::set< int > i_set;
do {
std::copy( i_set.begin(), i_set.end(),
std::eek:stream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
} while ( next_subset( i_set, i_vect ) );
}


Best

Kai-Uwe Bux
 
A

Alf P. Steinbach

* Gaijinco:
I use SIZE because Deitel/Deitel uses it. I know macros are usually in
uppercase, so I suppose that I can use a little hungarian notation and
write kSize, but your idea of letting the compiler count the size of
the array is even better!

I don't know anything about std::set, mind to tell me a little about
it?

#include <algorithm> // std::copy
#include <iterator> // std::eek:stream_iterator
#include <iostream> // std::cout
#include <ostream> // <<, std::endl
#include <set> // std::set

std::eek:stream& operator<<( std::eek:stream& stream, std::set<int> const& set )
{
stream << "{ ";
std::copy(
set.begin(), set.end(), std::eek:stream_iterator<int>( stream, " " )
);
stream << "}";
return stream;
}

void displaySubsetsOf( std::set<int> const& set )
{
// E.g. recursive code to display subsets.
}

int main()
{
int const values[] = {1, 2, 5};
int const size = sizeof( values )/sizeof( *values );
std::set<int> const set( values, values + size );

std::cout
<< "For the set " << set << " all possible sub sets are:"
<< std::endl;
displaySubsetsOf( set );
}

I also found this code hard to understand (and it doesn't seem to work
as I copy/paste it) What's the idea behind it?

Check each bit in turn. '&' is bitwise logical 'and'. '<<' is bitwise shift
left.

for( int j = 0; j < SIZE; ++j )
{
if( (i & (1 << j)) != 0 ) { cout << set[index] << " "; }
}

Typo, 'index' should be 'j':

#include <iostream>
#include <ostream>

int main()
{
using namespace std;

int const set[] = {1,2,5};
int const size = sizeof(set)/sizeof(*set);

cout << "For the set { 1 2 5 } all possible sub sets are:" << endl;

for( int i = 0; i < (1 << size); ++i )
{
cout << "{ ";
for( int j = 0; j < size; ++j )
{
if( (i & (1 << j)) != 0 ) { cout << set[j] << " "; }
}
cout << "}" << endl;
}
}
 
G

Greg

Gaijinco said:
I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
using namespace std;
#include <cmath>

int main(){

const int SIZE=3;
int set[SIZE]={1,2,5};

cout << "For the set { 1 2 5 } all possible sub sets are:" << endl;

for(int i=pow(SIZE,2)-1; i>=0; --i){
int index=2;
int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}
cout << "}" << endl;
}

system("pause");
return 0;
}

However it seems bulky to me. There is another way?

Thank you!

Yes, a template metaprogram is well suited for this kind of problem,
since the list of subsets can be computed at compile time. For the
purposes of contrast I threw together a simple metaprogram to
demonstrate how easily this can be done.

For anyone wishing to follow along at home, I used gcc 4.01 to compile
my suggested solution:

#include <tr1/tuple>
#include <iostream>

// a meta program if statement
template <bool, class T, class F> struct enable_if{};

template <class T, class F>
struct enable_if< true, T, F >
{ typedef T type; };

template <class T, class F>
struct enable_if< false, T, F >
{ typedef F type; };

// an integer "type" for set members
template <int I>
struct Integer
{
static const int value = I;
};

using std::tr1::tuple;
using std::tr1::tuple_element;
using std::tr1::tuple_size;

// a metafunction to pop the first tuple element

template <class T> struct PopFront {};

template <class T1, class T2, class T3, class T4, class T5,
class T6, class T7, class T8, class T9, class T10>
struct PopFront< tuple<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> >
{
typedef tuple<T2, T3, T4, T5, T6, T7, T8, T9, T10> type;
};

// a metafunction to push a new element to the front of a tuple

template <class T1, class T2> struct PushFront {};

template <class T, class T1, class T2, class T3, class T4,
class T5, class T6, class T7, class T8, class T9, class T10>
struct PushFront<T,tuple<T1, T2, T3, T4, T5, T6, T7, T8, T9,T10> >
{
typedef tuple<T, T1, T2, T3, T4, T5, T6, T7, T8, T9> type;
};

// constructs a subset tuple for the Set based on a Counter
template <class T, int Index>
struct Subset
{
typedef typename
enable_if<Index%2,
typename
PushFront<typename tuple_element<0,T>::type,
typename
Subset<typename PopFront<T>::type, Index/2>
::type>::type,
typename
Subset<typename PopFront<T>::type, Index/2>
::type>::type type;
};

// terminate Subset recursion
template <class T>
struct Subset<T, 0>
{
typedef tuple<> type;
};

// this routine prints out one subset
template <class T>
void PrintSubSet()
{
std::cout << " " << tuple_element<0, T>::type::value << ", ";
PrintSubSet< typename PopFront<T>::type >();
}

// terminate the subset recursion
template <>
void PrintSubSet< tuple<> >(){}

// prints all subsets
template <class T, int Counter,
int Limit = 1 << tuple_size<T>::value>
struct PrintAllSubSets
{
void operator()()
{
std::cout << "{";

PrintSubSet< typename Subset<T, Counter>::type>();

std::cout << "}" << std::endl;

PrintAllSubSets<T, Counter+1>()();
}
};

// terminate template recursion
template <class T, int Counter>
struct PrintAllSubSets<T, Counter, Counter>
{
void operator()() {}
};

// the "set" from the original example
typedef tuple< Integer<1>, Integer<2>, Integer<5> > Set;

int main()
{
PrintAllSubSets<Set, 0>()();
}

// Here is the (correct) output from executing the above program.

{}
{ 1, }
{ 2, }
{ 1, 2, }
{ 5, }
{ 1, 5, }
{ 2, 5, }
{ 1, 2, 5, }


//

And this program was even easier to write than it looks.

Greg
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top