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