show all subset of a set

[mary8shtr]

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;
}

 

[Öö Tiib]

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

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.

 

[Jorgen Grahn]

A program is a set of all subsets of this part of the show.
....
int main()

{
int testcase=0;
int n;
ar *a;
a=new ar [2000];

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

 

[Stefan Ram]

this program should be solved with tow way.

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!

 

[David Brown]

with throw-away (code)?

Don't you mean with "throw-up" 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!

 

[David Brown]

On 06/02/14 17:13, (e-mail address removed) 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.

 

[Dale Fletcher]

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.

Good observation. Then there is a question of unmasking the bits.

 

[Stefan Ram]

Good observation. Then there is a question of unmasking the bits.

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.

 

[Öö Tiib]

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.

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.

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.

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.

 

[Stefan Ram]

It is quite optimal to use 'enum', 'std::bitset<32>' or just

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 ); }

 

[Öö Tiib]

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

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.

 

[J. Clarke]

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!)

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.