Subset Algorithm

[sara22]

Hi all,
I am trying to find the algorithm which
print all subsets of a given set of n objects
for example the set A={a1,a2,a3}
the output is:
{}
{a1}
{a2}
{a3}
{a1,a2}
{a1,a3}
{a2,a3}
{a1,a2,a3}


Best regards,
sara

[Hnefi]

Oh my, for a moment there I thought I was back studying LISP. I had to solve this exact problem in my LISP course.

The solution below is very easy to do in languages such as Lisp and Haskell. In C/C++, it might not be the best way. It also depends on how your sets are implemented. Are they arrays? Linked lists? Some special set class?

Anyway, on to the solution. I assume it doesn't matter in which order the output is given. Recursion is usually a good approach for this kind of problem. I won't give you the exact algorithm, but close.

First, if the set (I will call it I) is empty, simply return I.

Then, save a second set (let's call it set R). Let set R be the set of subsets of I minus the first element. In other words, if your function is called P(I), you would let R be P(I - I[0]). This is the recursion.

Then, append the first element of I to each subset of I. This can be done with an auxilary function - I'll call it addtoeach(element, set) and go through it later.

Finally, return R. In some languages, this will automatically output R. If the language you use does not, then you will need to write a "starting function" that calls P(I) and outputs each element in the set that P returns. Each element in that set will itself be a set.

Last but not least, the function addtoeach(element, set). This one is easy. If the set is empty, simply return nil/null/nothing. Otherwise, return (element + set[0]) + addtoeach(element, set - set[0]).

As I said, this is a very "lispy" solution, where the sets would be implemented in the very powerful lists that LISP supports. Whether or not it is practical in the language you use depends on how the set datatype is implemented.

[omshivaprasad]

Well,
the answer to the question is similar to the implementation of enum type in C language.

take a bit stream of length equal to the number of elements in the set.
(!Hope the elements are less than 32)

int bitstream;

int min=0;
int max = pow(2, no of elements ) -1;

for(int i=min;i<=max;i++)
{
parse i value,
each bit represents whether an element in the set is present or not.
display all elements.

Use bit wise operations to extract each.

this method is very efficient since only bit wise operations are involved and no additional memory is required..


}

[Hnefi]

Man, that was a clever solution. Why didn't I think of that?

[sara22]

Thank u very much for ur answer