subsets of array

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

re: subsets of array

* Jessica Weiner:[color=blue]
> I have an array of n integers and I want a function that returns a list of
> arrays of all possible subsets.[/color]

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.

[color=blue]
> Can someone provide me with the code?[/color]

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?

re: subsets of array

Alf P. Steinbach wrote:[color=blue]
> 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.[/color]

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.

re: subsets of array

Jessica Weiner wrote:

[color=blue]
> 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.[/color]



Wow, very speedy in getting into the old killfile.


*plonk*



Brian

re: subsets of array

Jessica Weiner wrote:[color=blue]
> Alf P. Steinbach wrote:[color=green]
> > 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.[/color]
>
> 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.[/color]

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

re: subsets of array

dragoncoder wrote:[color=blue]
> Stupid ?? Do you know who you are talking to ?[/color]

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

re: subsets of array

Jessica Weiner wrote:[color=blue]
> dragoncoder wrote:[color=green]
> > Stupid ?? Do you know who you are talking to ?[/color]
>
> I am talking to Stupid...... STUPID.[/color]

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.

re: subsets of array

"Jessica Weiner" <jessica@gmail.com> wrote in message
news:jra2g.18420$tN3.12058@newssvr27.news.prodigy. net...[color=blue]
> dragoncoder wrote:[color=green]
> > Stupid ?? Do you know who you are talking to ?[/color]
>
> I am talking to Stupid...... STUPID.
>
>[/color]

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

re: subsets of array

BigBrian wrote in message ...[color=blue]
>
>Jessica Weiner wrote:[color=green]
>> dragoncoder wrote:[color=darkred]
>> > Stupid ?? Do you know who you are talking to ?[/color]
>>
>> I am talking to Stupid...... STUPID.[/color]
>
>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.[/color]


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

re: subsets of array

BobR wrote:[color=blue]
> BigBrian wrote in message ...[color=green]
> >
> >Jessica Weiner wrote:[color=darkred]
> >> dragoncoder wrote:
> >> > Stupid ?? Do you know who you are talking to ?
> >>
> >> I am talking to Stupid...... STUPID.[/color]
> >
> >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.[/color]
>
>
> 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[/color]

The most wonderful code I read today.

re: subsets of array

Jessica Weiner posted:
[color=blue]
> 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?[/color]

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

re: subsets of array

On Fri, 21 Apr 2006 19:32:31 GMT "Jessica Weiner" <jessica@gmail.com>
waved a wand and this message magically appeared:
[color=blue]
> dragoncoder wrote:[color=green]
> > Stupid ?? Do you know who you are talking to ?[/color]
>
> I am talking to Stupid...... STUPID.[/color]

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.

re: subsets of array

Salt_Peter wrote:[color=blue]
> 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!
> ).[/color]

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

re: subsets of array

Tomás wrote:[color=blue]
> 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.[/color]

Thanks!

re: subsets of array

> NumberType *p = new NumberType[ very_big_number ];[color=blue]
> //Ask a mathematician how to calculate very_big_number[/color]


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

re: subsets of array

Tomás wrote:[color=blue][color=green]
> > NumberType *p = new NumberType[ very_big_number ];
> > //Ask a mathematician how to calculate very_big_number[/color]
>
>
> 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.[/color]

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.

re: subsets of array

lichaoji@gmail.com wrote in message ...[color=blue]
>
>BobR wrote:[color=green]
>> #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[/color]
>
>The most wonderful code I read today.[/color]

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!

re: subsets of array

Jessica Weiner wrote:[color=blue]
> Salt_Peter wrote:[color=green]
> > 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!
> > ).[/color][/color]
[color=blue]
> 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.[/color]

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.

re: subsets of array

> Jessica Weiner wrote:[color=blue]
> 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.[/color]

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

~Jessica
(yeah right)

re: subsets of array

Jessica Weiner wrote:[color=blue]
> 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[/color]

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.

re: subsets of array

Markus Schoder <a3vr6dsg-usenet@yahoo.de> wrote:[color=blue]
> 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.[/color]

Yes, this is known as the Power Set.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

re: subsets of array

"BobR" <RemoveBadBobR@worldnet.att.net> writes:
[color=blue]
> BigBrian wrote in message ...[/color]

[color=blue]
> #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;
> }
>[/color]

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

re: subsets of array

TJW ha scritto:
[color=blue]
> "BobR" <RemoveBadBobR@worldnet.att.net> writes:
>[color=green]
> > BigBrian wrote in message ...[/color]
>
>[color=green]
> > #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;
> > }
> >[/color]
>
> 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[/color]


<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

re: subsets of array

TJW wrote in message ...[color=blue]
>"BobR" <RemoveBadBobR@worldnet.att.net> writes:[color=green]
>> #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;
>> }
>>[/color]
>
> 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[/color]

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

re: subsets of array

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

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.

re: subsets of array

Hello,

"BobR" <RemoveBadBobR@worldnet.att.net> writes:
[color=blue]
> 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.
>[/color]
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.
[color=blue]
> The default parameter in the arg list (int array = 43) is just for
> distraction, it don't do nuthin' <G>
>[/color]
Yeah ... things started to come back to me after MeDevil's post.
[color=blue]
> 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[/color]

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