show all subset of a set

Discussion in 'C++' started by mary8shtr, Feb 6, 2014.

  1. mary8shtr

    mary8shtr Guest

    A program is a set of all subsets of this part of the show. Users can entera number., For example, if n = 2 the output looks like this:
    {}
    {1}
    {2}
    {1,2}
    or for n=3 we have:
    {}
    {1}
    {2}
    {3}
    {1,2}
    {1,3}
    {2,3}
    {1,2,3}
    meantime this program should be solved with tow way.
    recursive function and Non-recursive.Can also be used in solving the problem of bitwise operations.

    my algorithm that is for per subset exists one number. these numbers are form 0 until (2^n)-1.allow me explain it with a example.
    n=3
    { } 000 0
    {1} 100 4
    {2} 010 2
    {3} 001 1
    {1,2} 110 6
    {1,3} 101 5
    {2,3} 011 3
    {1,2,3} 111 7
    The third column show some number(fn) that i use in code.now we know per number of subset has to state(sn).0 or 1. this means it exists or not exists.now i should match fn and sn.and suggested way is use of bitwise operators.(operator &).and now i don't know what do and thing with else thing.
    #include <iostream>
    using namespace std;
    #include <conio.h>
    #include <string.h>
    int pow(int a,int b)
    {
    int p=1;
    for(int i=0;i<b;i++)
    p=p*a;
    return p;
    }
    struct ar
    {
    int binary;
    int content;
    };
    int main()

    {
    int testcase=0;
    int n;
    ar *a;
    a=new ar [2000];
    cin>>testcase;
    int i=0;
    while(i<testcase)
    {
    cin>>n;
    for(int j=0,k=1;j<n;j++,k++)
    {
    a[j].content=k;
    a[j].binary=2;
    }


    for(int p=0;p<pow(2,n)-1;p++)
    {
    cout<<'{';
    for(int m=0;m<n;m++)
    {

    int b;
    b=a[m].binary&p;
    if(b==1)
    cout<<a.content<<' ';

    }
    cout<<'}';
    }

    cout<<endl;
    i++;
    }
    return 0;
    }
     
    mary8shtr, Feb 6, 2014
    #1
    1. Advertisements

  2. mary8shtr

    Öö Tiib Guest

    Your illustration seems messed up. Usually we expect to
    see that:
    n=3
    set binary decimal
    { } 000 0
    {1} 001 1
    {2} 010 2
    {1,2} 011 3
    {3} 100 4
    {1,3} 101 5
    {2,3} 110 6
    {1,2,3} 111 7

    Lower sub-patterns repeat so it is simple to make it recursive.
    Also like we see the decimal is now linear so it is pointless to
    make it recursive. ;)
     
    Öö Tiib, Feb 6, 2014
    #2
    1. Advertisements

  3. mary8shtr

    Jorgen Grahn Guest

    Where do they teach people to do it like this?

    There are at least two simpler, safer and more obvious ways of getting
    an array of 2000 objects:

    1. Use a plain old C array:

    ar a[2000];

    2. Use std::vector:

    std::vector<ar> a(2000);

    3. Things which were invented after 1998, like std::array. I haven't
    learned to use them so I cannot come with suggestions.

    I realize this wasn't the core of the question. I didn't read it,
    and it didn't seem very clear. Sorry.

    /Jorgen
     
    Jorgen Grahn, Feb 6, 2014
    #3
  4. mary8shtr

    Stefan Ram Guest

    with throw-away (code)?

    #include <iostream> // ::std::cout
    #include <ostream> // <<
    #include <cassert> // assert
    #include <new> // ::std::nothrow

    void print( int const set[], size_t const n, size_t const m )
    { size_t j; int * c = new( ::std::nothrow )int[ n + 3 ];
    if( c != nullptr )
    { assert( m >= n ); for( j = 1; j <= n; ++j )c[ j ]= j - 1;
    c[ n + 1 ]= m; c[ n + 2 ]= 0; loop: goto visit;
    next: for( j = 1; c[ j ]+ 1 == c[ j + 1 ]; ++j )c[ j ]= j - 1;
    if( j > n )goto end; c[ j ]= c[ j ]+ 1; goto loop;
    visit: for( size_t i = 1; i <= n; ++i )::std::cout << set[ c[ i ]];
    ::std::cout << "\n";
    goto next; end: delete[] c; }}

    int main()
    { int const set[] ={ 1, 2, 3 }; size_t const m = sizeof set / sizeof 0[ set ];
    for( size_t size = 0; size <= m; ++size )print( set, size, m ); }

    The first time ever I used array new and array delete in a program,
    hope I got it right!
     
    Stefan Ram, Feb 7, 2014
    #4
  5. mary8shtr

    David Brown Guest

    Don't you mean with "throw-up" code? :)
     
    David Brown, Feb 7, 2014
    #5
  6. mary8shtr

    David Brown Guest

    On 06/02/14 17:13, wrote:

    You've already been given some help about the problem itself, but let me
    give you a little advice on style. The biggest key on your keyboard is
    the space key - learn to use it. If you get in the habit of laying out
    your code clearly and neatly /now/, your code will be far more readable
    - leading to fewer errors (and higher marks for your homework).

    Here are a couple of example style guides:

    <https://www.kernel.org/doc/Documentation/CodingStyle>
    <http://httpd.apache.org/dev/styleguide.html>

    These are both for C, rather than C++ - but for this purpose C is a
    subset of C++, and these guides are shorter than C++ style guides.

    You don't necessarily have to agree with these guides on everything
    (they don't agree with each other on everything), but learn from them.
    And pretty much /every/ style guide agrees on the use of spaces.
     
    David Brown, Feb 7, 2014
    #6
  7. Good observation. Then there is a question of unmasking the bits.
     
    Dale Fletcher, Feb 8, 2014
    #7
  8. mary8shtr

    Stefan Ram Guest

    Do we need vectors assuming that 64-bit integer arithmetic
    is available? On one hand, some sets might have more than
    64 elements. (In 1997, Harkstrøm et al. reported a set with
    more than 3000 elements!) On the other hand, printing all
    subsets from a set with more than 64 elements might take
    such a long time that it is practically unfeasible, so that
    we might not have to worry at all about implementing this.

    When one can print 1e9 lines per second (each line containing
    a subset specification), it might still take more than
    200000 years to print all subsets of a set with 64 elements.
    However, during that time computers might become faster,
    so that the task could be finished earlier, when the computer
    is updated using hot hardware update capabilities while it
    executes the program.
     
    Stefan Ram, Feb 9, 2014
    #8
  9. mary8shtr

    Öö Tiib Guest

    It is quite optimal to use 'enum', 'std::bitset<32>' or just
    'uint32_t' instead of 'std::set<type_that_has_32_states>'. Also
    that 'std::bitset<3000>' can be often more viable than
    'std::set<type_that_has_3000_states>'. Instead of 'std::vector'
    I would suggest 'boost::container::flat_set' that takes care
    of set-like behavior of underlying vector there.
    The task to output all possible states of a set is indeed not too
    useful when the amount of states grows. Learning to output state
    of set (in all of its incarnations) is the handy skill there.
     
    Öö Tiib, Feb 9, 2014
    #9
  10. mary8shtr

    Stefan Ram Guest

    With <cstdint>::std::uint_least64_t one can do arithmetics
    and get the next state by just »++«.

    #include <iostream>
    #include <ostream>
    #include <cstdint>
    #include <cassert>

    void print( int const i, int const num )
    { for( int k = num - 1; k >= 0; --k )
    ::std::cout <<( char )( i &( 1 << k )? '`' + num - k : ' ' );
    ::std::cout << '\n'; }

    void enumerate( int const num )
    { assert( num <= 64 );
    using bits = ::std::uint_least64_t;
    bits const top =( bits )1 << num;
    for( bits i = 0; i <= top - 1; ++i )print( i, num ); }

    int main(){ enumerate( 3 ); }
     
    Stefan Ram, Feb 9, 2014
    #10
  11. mary8shtr

    Öö Tiib Guest

    Yes, that was my original point in start of this sub-thread.

    In practice we rarely need to order states of set (nothing to
    talk of finding next state of set). In practice we usually
    need to insert, erase and count elements in it.

    Inserting to integral variable used as set is done with '|='
    erasing with '&=~' but efficient counting is tricky and I
    bet that 'std::bitset' does it more efficiently than algorithm
    of average Joe. ;)
     
    Öö Tiib, Feb 9, 2014
    #11
  12. mary8shtr

    J. Clarke Guest

    Are you talking about some special kind of set here? The integers
    constitute a set with infinitely many elements. The reals also
    constitute such a set with the integers as a proper subset (note that
    {the integers that can be represented with 64-bit arithmetic} and {the
    reals that can be represented with IEEE floating point} are both finite
    sets but both contain considerably more than 64 elements). Then there
    is the set {humans} with more than 6 billion, the set {galaxies} with
    "billions and billions", and the set {stars} which has "billions and
    billions" in each galaxy.
     
    J. Clarke, Feb 17, 2014
    #12
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.