Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
show all subset of a set
87 views
Skip to first unread message
mary...@gmail.com
Feb 6, 2014, 11:13:54 AM2/6/14
to
A program is a set of all subsets of this part of the show. Users can enter a 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[i].content<<' ';
}
cout<<'}';
}
cout<<endl;
i++;
}
return 0;
}
{}
{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[i].content<<' ';
}
cout<<'}';
}
cout<<endl;
i++;
}
return 0;
}
Öö Tiib
Feb 6, 2014, 11:48:50 AM2/6/14
to
On Thursday, 6 February 2014 18:13:54 UTC+2, mary...@gmail.com wrote:
> 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
> 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
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
Feb 6, 2014, 11:49:59 AM2/6/14
to
On Thu, 2014-02-06, mary...@gmail.com wrote:
> A program is a set of all subsets of this part of the show.
...
> 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?
>
> {
> int testcase=0;
> int n;
> ar *a;
> a=new ar [2000];
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 <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Message has been deleted
David Brown
Feb 7, 2014, 3:20:51 AM2/7/14
to
On 07/02/14 06:38, Stefan Ram wrote:
> 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!
>
> 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
Feb 7, 2014, 3:29:39 AM2/7/14
to
On 06/02/14 17:13, mary...@gmail.com 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.
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
Feb 8, 2014, 3:17:08 PM2/8/14
to
Message has been deleted
Öö Tiib
Feb 9, 2014, 6:13:44 AM2/9/14
to
On Sunday, 9 February 2014 10:39:48 UTC+2, Stefan Ram wrote:
> 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.
> Dale Fletcher <dfl...@twees.au> writes:
> >Good observation. Then there is a question of unmasking the bits.
>
> Do we need vectors assuming that 64-bit integer arithmetic
> >Good observation. Then there is a question of unmasking the bits.
>
> 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.
Message has been deleted
Öö Tiib
Feb 9, 2014, 7:20:58 AM2/9/14
to
On Sunday, 9 February 2014 13:46:59 UTC+2, Stefan Ram wrote:
> 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. ;)
> 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
Feb 17, 2014, 8:18:21 AM2/17/14
to
In article <subsets-201...@ram.dialup.fu-berlin.de>,
r...@zedat.fu-berlin.de says...
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.
> 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.
>
r...@zedat.fu-berlin.de says...
>
> Dale Fletcher <dfl...@twees.au> writes:
> >Good observation. Then there is a question of unmasking the bits.
>
> Dale Fletcher <dfl...@twees.au> writes:
> >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!)
Are you talking about some special kind of set here? The integers
> 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!)
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.
> 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.
>
0 new messages