Generate All Subsets

Discussion in 'C++' started by Gaijinco, Sep 26, 2005.

  1. Gaijinco

    Gaijinco Guest

    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!
    Gaijinco, Sep 26, 2005
    #1
    1. Advertising

  2. * 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.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Sep 26, 2005
    #2
    1. Advertising

  3. On Mon, 26 Sep 2005 15:53:08 GMT, (Alf P. Steinbach)
    wrote:

    >> int main(){
    >>
    >> const int SIZE=3;

    >
    >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.

    --
    Bob Hairgrove
    Bob Hairgrove, Sep 26, 2005
    #3
  4. Gaijinco wrote:
    > 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
    John Harrison, Sep 26, 2005
    #4
  5. Gaijinco

    Gaijinco Guest

    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.
    Gaijinco, Sep 26, 2005
    #5
  6. Gaijinco

    Kai-Uwe Bux Guest

    Gaijinco wrote:

    > 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
    Kai-Uwe Bux, Sep 26, 2005
    #6
  7. * 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;
    }
    }

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Sep 26, 2005
    #7
  8. Gaijinco

    Greg Guest

    Gaijinco wrote:
    > 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
    Greg, Sep 27, 2005
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger Varley
    Replies:
    20
    Views:
    895
    jan V
    Aug 14, 2005
  2. will

    xsl subsets of nodesets

    will, Jul 7, 2003, in forum: XML
    Replies:
    3
    Views:
    848
    Marrow
    Jul 8, 2003
  3. Gaijinco

    Generate All Subsets

    Gaijinco, Sep 26, 2005, in forum: C Programming
    Replies:
    7
    Views:
    551
    Emmanuel Delahaye
    Sep 26, 2005
  4. Patrick

    search all subsets?

    Patrick, Dec 21, 2007, in forum: C++
    Replies:
    4
    Views:
    388
    Kira Yamato
    Dec 22, 2007
  5. joe chesak

    All contiguous subsets

    joe chesak, Mar 25, 2010, in forum: Ruby
    Replies:
    4
    Views:
    145
    joe chesak
    Mar 26, 2010
Loading...

Share This Page