powerset

Discussion in 'C++' started by Gunnar G, Aug 9, 2005.

  1. Gunnar G

    Gunnar G Guest

    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?
     
    Gunnar G, Aug 9, 2005
    #1
    1. Advertising

  2. 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 << " ";
    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 );
    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
     
    Karl Heinz Buchegger, Aug 9, 2005
    #2
    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. matt

    powerset operation

    matt, Jan 17, 2004, in forum: Perl
    Replies:
    0
    Views:
    1,312
  2. Tim Rowe

    Powerset

    Tim Rowe, Sep 15, 2003, in forum: Python
    Replies:
    0
    Views:
    543
    Tim Rowe
    Sep 15, 2003
  3. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    6
    Views:
    1,017
    Carsten Haese
    Jul 13, 2007
  4. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    0
    Views:
    434
    Evan Klitzke
    Jul 13, 2007
  5. Evan Klitzke

    Re: Fast powerset function

    Evan Klitzke, Jul 13, 2007, in forum: Python
    Replies:
    1
    Views:
    396
    Mark Dickinson
    Jul 14, 2007
Loading...

Share This Page