Generate All Subsets

[Gaijinco]

I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
using namespace std;
#include <cmath>

int main(){

const int SIZE=3;
int set[SIZE]={1,2,5};

for(int i=pow(SIZE,2)-1; i>=0; --i){
int index=2;
int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}
cout << "}" << endl;
}

system("pause") ;
return 0;
}

However it seems bulky to me. There is another way?

Thank you!

[Walter Roberson]

In article <11************ **********@g49g 2000cwa.googleg roups.com>,
Gaijinco <ga******@gmail .com> wrote:

I been thinking about this topic for a long time. The best I have done
is the following code: #include <iostream>
using namespace std;
#include <cmath>
Unfortunately that is C++ code, and this is the C language newsgroup.
system("pause") ;
Although system() is a standard C library call, the behaviour it
invokes is system-dependant. In particular, "pause" is not a
particularily widely supported system command.
However it seems bulky to me. There is another way?

You did not actually state what problem you are trying to solve,
at least not in clear terms. You also didn't indicate what the
restrictions were -- how big of a set does the code need to be
able to handle?

You might find, by the way, that the code is a lot cleaner if
you use the binary operators.
--
Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson

[Martin Ambuhl]

Gaijinco wrote:

I been thinking about this topic for a long time.
Then think longer. You have posted to comp.lang.c and
The best I have done
is the following code:
"your best" starts with 3 lines which are C++. The second line is a
syntax error in C; the first and third #include non-standard headers.
#include <iostream>
using namespace std;
#include <cmath>
I have rewritten your code in C, removing the wasteful (in time and
space) call of pow(), fixing your left shifts of the undefined variable
'cout'. I have not moved the declaration of the loop control variable,
even though a syntax error before C99.

#include <stdio.h>

int main(void)
{

int set[] = { 1, 2, 5 };
const int setsize = sizeof set / sizeof *set;

for (int /* warning: declaration assumes C99 */ i =
(1 << setsize) - 1 /* removed use of pow() */ ;
i >= 0; --i) {
int index = 2;
int n = i;
putchar('{');;
while (n > 0) {
if (n % 2)
printf("%d ", set[index]);
--index;
n /= 2;
}
puts("}");
}

return 0;
}
[OP's code continues]

int main(){

const int SIZE=3;
int set[SIZE]={1,2,5};

for(int i=pow(SIZE,2)-1; i>=0; --i){
int index=2;
int n=i;
cout << "{ ";
while(n>0){
if(n%2)
cout << set[index] << " ";
--index;
n/=2;
}
cout << "}" << endl;
}

system("pause") ;
return 0;
}

[Flash Gordon]

Gaijinco wrote:

I been thinking about this topic for a long time. The best I have done
is the following code:

#include <iostream>
Not a standard C header.
using namespace std;

<snip>

Not C.

I think you walked through the wrong door, comp.lang.c++ is just down
the hall to your left. However, you should check their FAQ and a few
days posts before you post there. You can't have done that here or you
would have known that we discuss C.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[SM Ryan]

# However it seems bulky to me. There is another way?

Bulky is an aesthetic concern. You got the primary issue that
binary representations of 0..2^(n-1) model the power set 2^S
where |S|=n. Using machine integers restricts |S| is to a small
integer; the arithmetic is simple enough you can actually
represent the numbers with arbitrary length byte strings.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
I have no idea what you just said.
I get that alot.

[Gaijinco]

Thank you for your posts! I apologize but all the c++ code, I post it
here because what I thought was important was the essence of the
problem and not the syntaxis. Again: my mistakes and I apologize.

You did not actually state what problem you are trying to solve,
at least not in clear terms. You also didn't indicate what the
restrictions were -- how big of a set does the code need to be
able to handle?
The problem is that given a set you must construct (print, whatever)
all possible subsets. The main issue is not size limitations but "how"
I have rewritten your code in C, removing the wasteful (in time and
space) call of pow(), fixing your left shifts of the undefined variable
'cout'. I have not moved the declaration of the loop control variable,
even though a syntax error before C99.

OK, using (1 << setsize) -1 in exchange of pow() is pretty neat .
Thanks! But I'm in what is a C99.

Then again, the answer is still unresolved: There is another way to
construct all possible subsets?

[Eric Sosman]

Gaijinco wrote On 09/26/05 14:33,:

[...]
Then again, the answer is still unresolved: There is another way to
construct all possible subsets?

Of course there are other ways, but your question is
about algorithms, not about C. If you find another way
and have questions about how to implement it in C, come
back and ask. (If you have questions about how to do it
in C++, ask in comp.lang.c++ instead.)

<off-topic>

Consider a recursive solution. First, it's easy to
generate all the subsets of a one-element set: they are
the empty set and the set containing only the single
element. Next, once you have a way to generate all the
subsets of an N-element set it's easy to generate all
the subsets of an (N+1)-element set: they are all the
given subsets "as is," plus those same subsets but with
the (N+1)st element added to each.

Remember, you asked only for "another way," not for
"another good way" ...

</off-topic>

--
Er*********@sun .com

[Emmanuel Delahaye]

Gaijinco wrote on 26/09/05 :

#include <iostream>

c++ is next door...

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"Mal nommer les choses c'est ajouter du malheur au
monde." -- Albert Camus.