Subsets

[nuaz]

Hi all,

i've a simple problem to solve but i'm a bit rusty with algorithms and i can't figure it out yet.
I have to calculate all the subset of a note set.

for example:

S = [A,B,C,D,E]

i need all the subsets of all cardinality like [A,B,C,D,E,AB,AC,AD,AE,BC,BD,BE,CD,CE,DE,ABC,ABD .... and so on..]

i use c# as programming language but obviously all kind of answers are very accepted.

any help ?

thanks

[Peter_B]

There is a very straightforward algorithm for this. If you have n members, then there will be 2^n subsets (including the empty set). You can map the subsets to the numbers 0 to 2^n, like this example for n=3:


ABC
000 {}
001 {C}
010 {B}
011 {BC}
100 {A}
101 {AC}
110 {AB}
111 {ABC}


The 1s and 0s indicate whether the corresponding member of the set is in each subset.

So, the algorithm is to generate the binary sequence in some way (see http://www.codeguru.com/forum/showthread.php?t=469910 if you aren't sure how to do this), and for each binary number create the corresponding subset.

Note that this method will not produce the list in order of subset size, so you might need to stick them into a container of some sort and them sort them. If you used a container such as std::set in C++ you wouldn't even have to do the sorting as the container is automatically sorted.

Or, you could use the algorithm here (http://www.applied-math.org/subset.pdf) to create the subsets in a different order - the Banker's sequence in this paper will give the subset in order of size (i.e. A,B,C,AB,AC,BC,ABC)