By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,044 Members | 1,291 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,044 IT Pros & Developers. It's quick & easy.

subsets of array

P: n/a
I have an array of n integers and I want a function that returns a list of
arrays of all possible subsets. Can someone provide me with the code?

Thanks.
Jess
Apr 21 '06 #1
Share this Question
Share on Google+
25 Replies


P: n/a
* Jessica Weiner:
I have an array of n integers and I want a function that returns a list of
arrays of all possible subsets.
The number of possible subsets is exponential in n: how much memory do
you think that will require?

Since this is obviously HOMEWORK (see this group's FAQ before posting,
please) I'll leave it to you to figure out exactly what the formula is.

It's probably also stated in your textbook.

Can someone provide me with the code?


Yes, but /will/ someone do your HOMEWORK for you?

Hopefully not.

See the FAQ's item about posting HOMEWORK questions.

--
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?
Apr 21 '06 #2

P: n/a
Alf P. Steinbach wrote:
Since this is obviously HOMEWORK (see this group's FAQ before posting,
please) I'll leave it to you to figure out exactly what the formula
is.


Its not homework, you dumbass. If you cannot help someone then simply keep
your mouth shut because it only goes to show how stupid you are.
Apr 21 '06 #3

P: n/a
Jessica Weiner wrote:

Its not homework, you dumbass. If you cannot help someone then simply
keep your mouth shut because it only goes to show how stupid you are.


Wow, very speedy in getting into the old killfile.
*plonk*

Brian
Apr 21 '06 #4

P: n/a

Jessica Weiner wrote:
Alf P. Steinbach wrote:
Since this is obviously HOMEWORK (see this group's FAQ before posting,
please) I'll leave it to you to figure out exactly what the formula
is.


Its not homework, you dumbass. If you cannot help someone then simply keep
your mouth shut because it only goes to show how stupid you are.


Stupid ?? Do you know who you are talking to ?

Apr 21 '06 #5

P: n/a
dragoncoder wrote:
Stupid ?? Do you know who you are talking to ?


I am talking to Stupid...... STUPID.
Apr 21 '06 #6

P: n/a

Jessica Weiner wrote:
dragoncoder wrote:
Stupid ?? Do you know who you are talking to ?


I am talking to Stupid...... STUPID.


Boy, that attitude will really get you what you asked.

Even if your original post wasn't about homework, asking for "code that
does [insert whatever here]" that is not what this group is about.
Calling somebody stupid is even less what it's about. When you have a
C++ question, or C++ topic to discouss, come back, otherwise go away.

Apr 21 '06 #7

P: n/a

"Jessica Weiner" <je*****@gmail.com> wrote in message
news:jr*******************@newssvr27.news.prodigy. net...
dragoncoder wrote:
Stupid ?? Do you know who you are talking to ?


I am talking to Stupid...... STUPID.


If he is stupid as you claim then try conducting a simple search on he who
you are calling stupid. You'll be surprised ( i guarentee it! ). Then
consider what "class" we should put you in since everything is relative,
after all.

My 8 year-old nephew can generate a better structured question than the
ridiculous quest you put forth. Additionally, if you can't serve yourself
nor gain a little maturity then... GROW UP, ASSHOLE !!!
Apr 22 '06 #8

P: n/a

BigBrian wrote in message ...

Jessica Weiner wrote:
dragoncoder wrote:
> Stupid ?? Do you know who you are talking to ?


I am talking to Stupid...... STUPID.


Boy, that attitude will really get you what you asked.

Even if your original post wasn't about homework, asking for "code that
does [insert whatever here]" that is not what this group is about.
Calling somebody stupid is even less what it's about. When you have a
C++ question, or C++ topic to discouss, come back, otherwise go away.

Now Brian, don't be so short(yup, a pun). If they want code, give them code:

#include <iostream> // C++
#include <ostream> // std::endl

void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}

int main(){
Weiner(42);
return 0;
}

--
Bob R
POVrookie
Apr 22 '06 #9

P: n/a


BobR wrote:
BigBrian wrote in message ...

Jessica Weiner wrote:
dragoncoder wrote:
> Stupid ?? Do you know who you are talking to ?

I am talking to Stupid...... STUPID.


Boy, that attitude will really get you what you asked.

Even if your original post wasn't about homework, asking for "code that
does [insert whatever here]" that is not what this group is about.
Calling somebody stupid is even less what it's about. When you have a
C++ question, or C++ topic to discouss, come back, otherwise go away.

Now Brian, don't be so short(yup, a pun). If they want code, give them code:

#include <iostream> // C++
#include <ostream> // std::endl

void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}

int main(){
Weiner(42);
return 0;
}

--
Bob R
POVrookie


The most wonderful code I read today.

Apr 22 '06 #10

P: n/a
Jessica Weiner posted:
I have an array of n integers and I want a function that returns a list
of arrays of all possible subsets. Can someone provide me with the
code?


No, but I can give you a hand.
First start of with an array full of zeros:

unsigned array[5] = {};

Then increment the last int, so you have:

0 0 0 0 1

That's one of your arrays. Keep incrementing it until you reach the maximum
value for an unsigned int. The set it to zero and increment the int behind,
as follows:

0 0 0 0 65535

will become:

0 0 0 1 0

Then when that reaches:

0 0 0 65535 65535

Increment the one behind both of them, giving:
0 0 1 0 0
And that will eventually become:
0 0 65535 65535 65535

It would require a lot of memory to do this. I'm not a mathematician, but
maybe someone knows the equation to figure out how much.

If you want answers here, it's best to be polite.

-Tomás
Apr 22 '06 #11

P: n/a
On Fri, 21 Apr 2006 19:32:31 GMT "Jessica Weiner" <je*****@gmail.com>
waved a wand and this message magically appeared:
dragoncoder wrote:
Stupid ?? Do you know who you are talking to ?


I am talking to Stupid...... STUPID.


Oh yes! You're one of these women who thinks using their bodies will
get them anything they want. Well, HELLO! <sfx: knocks on your head>
You won't get what you want from here. We Nerds (let's not forget about
the Geeks either), have suffered enough at the hands of women like you.

ENOUGH is ENOUGH!

It's time we had Men's Lib, just to balance things out a little bit!

--
http://www.munted.org.uk

Take a nap, it saves lives.
Apr 22 '06 #12

P: n/a
Salt_Peter wrote:
If he is stupid as you claim then try conducting a simple search on
he who you are calling stupid. You'll be surprised ( i guarentee it!
).


When you are done sucking his dick, maybe then you can come talk to me and I
will have a more "structured" comment for you.

A simple google search on "Alf Steinbach" doesn't reveal anything
spectacular. It only shows that he has been active on the newsgroups for a
while, which makes me think that he doesnt have a real job so he wanders
around from newsgroup to newsgroup trying to get jerks like yourself to
respect him.

I feel sorry for your nephew to have such a stupid uncle.

~Jessica
Apr 22 '06 #13

P: n/a
Tomás wrote:
It would require a lot of memory to do this. I'm not a mathematician,
but maybe someone knows the equation to figure out how much.


Thanks!
Apr 22 '06 #14

P: n/a
> NumberType *p = new NumberType[ very_big_number ];
//Ask a mathematician how to calculate very_big_number

Actually it just occurred to me how to calculate this.

The "smallest" possibility will be:

0 0 0 0 0
And the largest possibility will be:
65535 65535 65535 65535 65535
If we think of this as a number system whose base is 65536, rather than 10,
and then give the digit 65535 the symbol K, then the number is:

KKKKK

If we want to convert that to decimal (base 10), then we use the following
formula:

65535 x 65535^0
+ 65535 x 65535^1
+ 65535 x 65535^2
+ 65535 x 65535^3
+ 65535 x 65535^4

So... if you have fives 16-Bit numbers, then "very_big_number" is a HUGE
number, something like a quadilion-trillion-gaziliion-mammillion-billion.

Best to use just a few 8-Bit numbers.
-Tomás
Apr 22 '06 #15

P: n/a
Tomás wrote:
NumberType *p = new NumberType[ very_big_number ];
//Ask a mathematician how to calculate very_big_number

Actually it just occurred to me how to calculate this.

The "smallest" possibility will be:

0 0 0 0 0
And the largest possibility will be:
65535 65535 65535 65535 65535
If we think of this as a number system whose base is 65536, rather than 10,
and then give the digit 65535 the symbol K, then the number is:

KKKKK

If we want to convert that to decimal (base 10), then we use the following
formula:

65535 x 65535^0
+ 65535 x 65535^1
+ 65535 x 65535^2
+ 65535 x 65535^3
+ 65535 x 65535^4

So... if you have fives 16-Bit numbers, then "very_big_number" is a HUGE
number, something like a quadilion-trillion-gaziliion-mammillion-billion.

Best to use just a few 8-Bit numbers.


It seems you are trying to enumerate all possible sets of integers with
a given number of elements whereas the original question was about the
subsets of a given set of integers (represented as an array), no?

E.g. the result for {1,2} would be the list {}, {1}, {2}, {1,2}. There
are by the way 2^n subsets of a set with n elements.

Apr 22 '06 #16

P: n/a

li******@gmail.com wrote in message ...

BobR wrote:
#include <iostream> // C++
#include <ostream> // std::endl

void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}

int main(){
Weiner(42);
return 0;
}
--
Bob R
POVrookie


The most wonderful code I read today.


Glad to see I'm not alone in the "need to get a life" catagory! <G>

[ we get *excited* when they say "stay tuned for scenes" at the end of
NCIS/CSI tv programs!! Wish sombody would send me a beer.]
--
Bob R
POVrookie
Q - How many Americans does it take to screw G. Bush into a light socket?
A - We may never know, Americans are outnumbered!
Apr 22 '06 #17

P: n/a
Jessica Weiner wrote:
Salt_Peter wrote:
If he is stupid as you claim then try conducting a simple search on
he who you are calling stupid. You'll be surprised ( i guarentee it!
).
A simple google search on "Alf Steinbach" doesn't reveal anything
spectacular. It only shows that he has been active on the newsgroups for a
while, which makes me think that he doesnt have a real job so he wanders
around from newsgroup to newsgroup trying to get jerks like yourself to
respect him.


Googling for a name is a good idea. It is actually such a good idea
that many employers do it with the names of job applicants. So I think
you have provided a valuable service to any potential future employer
that will now be able to easily figure out what kind of person you are
by googling your name and finding your posts in this newsgroup.

Apr 22 '06 #18

P: n/a
> Jessica Weiner wrote:
Googling for a name is a good idea. It is actually such a good idea
that many employers do it with the names of job applicants. So I think
you have provided a valuable service to any potential future employer
that will now be able to easily figure out what kind of person you are
by googling your name and finding your posts in this newsgroup.


And that is why strippers use fake names. Think of me as a usenet stripper.

~Jessica
(yeah right)
Apr 23 '06 #19

P: n/a

Jessica Weiner wrote:
I have an array of n integers and I want a function that returns a list of
arrays of all possible subsets. Can someone provide me with the code?

Thanks.
Jess


The number of possible combinations are:
sigma(n!/((n-i)!*i!), i = 1, n-1) + 1

You can write a code to translate this algorithm to generate subsets.

Apr 24 '06 #20

P: n/a
Markus Schoder <a3*************@yahoo.de> wrote:
It seems you are trying to enumerate all possible sets of integers with
a given number of elements whereas the original question was about the
subsets of a given set of integers (represented as an array), no?

E.g. the result for {1,2} would be the list {}, {1}, {2}, {1,2}. There
are by the way 2^n subsets of a set with n elements.


Yes, this is known as the Power Set.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Apr 24 '06 #21

P: n/a
TJW
"BobR" <Re***********@worldnet.att.net> writes:
BigBrian wrote in message ...
#include <iostream> // C++
#include <ostream> // std::endl

void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}

int main(){
Weiner(42);
return 0;
}


Please forgive a C programming who has been lurking for a while
to refresh his OO memory ... but what specifically will this print
and why? I see the recursive call, but am not used to initializing
variables in a function declaration ... will array be 43 always or
42, 43, 44, ... and with cout << will the integers be translated
into ASCII characters?

Sorry to ruin a good joke that I don't get ...

Thanks,
TJW
Apr 25 '06 #22

P: n/a

TJW ha scritto:
"BobR" <Re***********@worldnet.att.net> writes:
BigBrian wrote in message ...


#include <iostream> // C++
#include <ostream> // std::endl

void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}

int main(){
Weiner(42);
return 0;
}


Please forgive a C programming who has been lurking for a while
to refresh his OO memory ... but what specifically will this print
and why? I see the recursive call, but am not used to initializing
variables in a function declaration ... will array be 43 always or
42, 43, 44, ... and with cout << will the integers be translated
into ASCII characters?

Sorry to ruin a good joke that I don't get ...

Thanks,
TJW

<snip> but what specifically will this print and why?
it will print always a string... (the one between the two <<)

<snip> will array be 43 always or 42, 43, 44,
that's a default argument. if you don't provide it, the specified value
will be used.
array will be at the first call 42, then 43 and so on, until a stack
overflow will crash all...

<snip> and with cout << will the integers be translated into ASCII
characters?
they are already ascii characters... in fact that is a const array of
char (a string) :P

MeDevil

Apr 25 '06 #23

P: n/a

TJW wrote in message ...
"BobR" <Re***********@worldnet.att.net> writes:
#include <iostream> // C++
#include <ostream> // std::endl
void Weiner(int array = 43){
std::cout<<"33 33 33 75 78 79 76 80 32 33 101 114 "
"101 104 32 112 108 101 104 32 111 110 "
"32 115 116 101 103 32 101 100 117 116 "
"105 116 116 97 32 110 97 32 104 116 105 "
"119 32 116 111 105 100 105 32 110 65 "<<std::endl;
Weiner(array+1);
return;
}
int main(){
Weiner(42);
return 0;
}


Please forgive a C programming who has been lurking for a while
to refresh his OO memory ... but what specifically will this print
and why? I see the recursive call, but am not used to initializing
variables in a function declaration ... will array be 43 always or
42, 43, 44, ... and with cout << will the integers be translated
into ASCII characters?

Sorry to ruin a good joke that I don't get ...
Thanks,
TJW


I agree with the explanation that MeDevil gave you, so, I won't repeat it
here.
[ If you still 'don't get it', ask more. ]

To help you 'decode' the message, here is the code I used to get the numbers:

std::string Rev("< the secret string was here >");
std::reverse(Rev.begin(), Rev.end());
for(size_t i(0); i < Rev.size(); ++i){
std::cout<<int( Rev.at(i) )<<" ";
}
std::cout<<std::endl;

You could get back the 'ASCII' with something like:
std::cout<<char(65)<<char(110)<<std::endl; // etc.

The default parameter in the arg list (int array = 43) is just for
distraction, it don't do nuthin' <G>

Coming to C++ from C? Do you know about Mr. Eckel's book? (It was pretty much
designed to take you from C to C++)
Get "Thinking in C++", 2nd ed. Volume 1(&2) by Bruce Eckel
(available for free here. You can buy it in hardcopy too.):
http://www.mindview.net/Books/TICPP/...ngInCPP2e.html

--
Bob R
POVrookie
Apr 25 '06 #24

P: n/a
On Tue, 25 Apr 2006 21:02:58 GMT "BobR"
<Re***********@worldnet.att.net> waved a wand and this message
magically appeared:
The default parameter in the arg list (int array = 43) is just for
distraction, it don't do nuthin' <G>


arrayList.reverse();
for (std::list<int>::iterator i = arrayList.begin(); i !=
arrayList.end(); i++) std::cout << char(*i);

std::cout << "\n";

--
http://www.munted.org.uk

Take a nap, it saves lives.
Apr 25 '06 #25

P: n/a
TJW
Hello,

"BobR" <Re***********@worldnet.att.net> writes:
To help you 'decode' the message, here is the code I used to get the numbers:

std::string Rev("< the secret string was here >");
std::reverse(Rev.begin(), Rev.end());
for(size_t i(0); i < Rev.size(); ++i){
std::cout<<int( Rev.at(i) )<<" ";
}
std::cout<<std::endl;

You could get back the 'ASCII' with something like:
std::cout<<char(65)<<char(110)<<std::endl; // etc.
Thanks for the expansion ... hopefully I'll have a little time
tonight to kick my brain some more and work out what the string
should be.
The default parameter in the arg list (int array = 43) is just for
distraction, it don't do nuthin' <G>
Yeah ... things started to come back to me after MeDevil's post.
Coming to C++ from C? Do you know about Mr. Eckel's book? (It was pretty much
designed to take you from C to C++)
Get "Thinking in C++", 2nd ed. Volume 1(&2) by Bruce Eckel
(available for free here. You can buy it in hardcopy too.):
http://www.mindview.net/Books/TICPP/...ngInCPP2e.html


Thanks for the tip, my classes in college where in C++, but I
stick mainly with C for most of my work and haven't looked at OO
programming much since then. Just trying to get my sea legs back,
so to speak.

Thanks again for the tip,
TJW
Apr 25 '06 #26

This discussion thread is closed

Replies have been disabled for this discussion.