Hello all. While looking around for algorithms to calculate the power set of a set I came across the usual recursive algorithm which tries to exhaust all the probable sets and also its iterative version which does pretty much the same thing. But then I saw an algorithm that calculates the power set that is both simple to understand, fast and elegant and I felt the need to write about it and share a sample C implementation.

But first of all what exactly is a power set? For the whole explanation please visit the Wikipedia page. In short, the Power Set of a set *S* is all the possible subsets of that set including itself and the empty set. For example the power set of *S* = {3,4,5} is *P(S)* = { {3,4,5} , {3,4}, {4,5}, {3,5}, {3}, {4}, {5}, {∅} }. The number of subsets of the power set is given by 2^{s} where *s* is the number of elements in *S*. *s* is also called the cardinality of *S*.

The algorithm works in a very simple and elegant way. You represent the original set *S* with a string of bits all with a value of 1. For the above example of *S* that number would be what? 2^{s}-1 = 2^{3}-1 = 7. In binary seven is `111`

as we can see from the figure below.

Now just picture that each bit of this number is associated with one element of the original set. So in our example the first bit would be associated with 3, the second bit with 4 and so on. Now with a simple iteration from 0 to this number (7 in our case) we can iterate through all the possible permutations of the set by taking the binary number representation at each iteration and matching its bits to the existence(or not) of the corresponding elements of the set. Since pretty pictures are much better than words I made the following diagram to illustrate the algorithm in a graphic manner.

And just like that we can obtain the power set of any given set.

Let’s see a quick implementation that I cooked up in C.

#include <math.h> #include <stdio.h> //an example set int A[] = {1, 5, 7 , 8, 2, 10, 12}; //The function to calculate the subset of the original set //corresponding to the number given at num void printSet(unsigned int num,int* arr,unsigned int size) { unsigned int i; printf("\t{"); //for each bit for(i=0;i<sizeof(unsigned int)*8;i++) { if(num&(unsigned int)0x1)//if it's ON print the corresponding value { if(num >>1 ==0)//if it's the last ON bit {//print without comma and terminate the loop printf("%d",arr[i]); break; } else printf("%d,",arr[i]); } num = num>>1;//keep shifting right to get more bits } printf("}\n"); } int main() { unsigned int size,i,n; //get the cardinality of the set and check //if it can be represented by an unsigned int size = sizeof(A)/sizeof(int); if(size > sizeof(unsigned int)*8) { printf("The given set can not be represented by the size\ of unsigned int in the system\nQuitting ..."); return -1; } //get the number until which we need to iterate n = pow(2,size)-1; //calculate and print the powerset printf("The powerset of {"); for(i=0;i< size-1; i ++) printf("%d,",A[i]); printf("%d} is:\n{\n",A[size-1]); for(i=0;i<=n;i++) printSet(i,A,size); printf("}\n"); return 0; } |

The above is just a minimal example to demonstrate the algorithm. It should work in most C compilers, including GCC and MSVC and give the following output:

The powerset of {1,5,7,8,2,10,12} is:

{

{}

{1}

{5}

{1,5}

{7}

{1,7}

{5,7}

{1,5,7}

{8}

{1,8}

{5,8}

{1,5,8}

{7,8}

{1,7,8}

{5,7,8}

{1,5,7,8}

{2}

{1,2}

{5,2}

{1,5,2}

{7,2}

{1,7,2}

{5,7,2}

{1,5,7,2}

{8,2}

{1,8,2}

{5,8,2}

{1,5,8,2}

{7,8,2}

{1,7,8,2}

{5,7,8,2}

{1,5,7,8,2}

{10}

{1,10}

{5,10}

{1,5,10}

{7,10}

{1,7,10}

{5,7,10}

{1,5,7,10}

{8,10}

{1,8,10}

{5,8,10}

{1,5,8,10}

{7,8,10}

{1,7,8,10}

{5,7,8,10}

{1,5,7,8,10}

{2,10}

{1,2,10}

{5,2,10}

{1,5,2,10}

{7,2,10}

{1,7,2,10}

{5,7,2,10}

{1,5,7,2,10}

{8,2,10}

{1,8,2,10}

{5,8,2,10}

{1,5,8,2,10}

{7,8,2,10}

{1,7,8,2,10}

{5,7,8,2,10}

{1,5,7,8,2,10}

{12}

{1,12}

{5,12}

{1,5,12}

{7,12}

{1,7,12}

{5,7,12}

{1,5,7,12}

{8,12}

{1,8,12}

{5,8,12}

{1,5,8,12}

{7,8,12}

{1,7,8,12}

{5,7,8,12}

{1,5,7,8,12}

{2,12}

{1,2,12}

{5,2,12}

{1,5,2,12}

{7,2,12}

{1,7,2,12}

{5,7,2,12}

{1,5,7,2,12}

{8,2,12}

{1,8,2,12}

{5,8,2,12}

{1,5,8,2,12}

{7,8,2,12}

{1,7,8,2,12}

{5,7,8,2,12}

{1,5,7,8,2,12}

{10,12}

{1,10,12}

{5,10,12}

{1,5,10,12}

{7,10,12}

{1,7,10,12}

{5,7,10,12}

{1,5,7,10,12}

{8,10,12}

{1,8,10,12}

{5,8,10,12}

{1,5,8,10,12}

{7,8,10,12}

{1,7,8,10,12}

{5,7,8,10,12}

{1,5,7,8,10,12}

{2,10,12}

{1,2,10,12}

{5,2,10,12}

{1,5,2,10,12}

{7,2,10,12}

{1,7,2,10,12}

{5,7,2,10,12}

{1,5,7,2,10,12}

{8,2,10,12}

{1,8,2,10,12}

{5,8,2,10,12}

{1,5,8,2,10,12}

{7,8,2,10,12}

{1,7,8,2,10,12}

{5,7,8,2,10,12}

{1,5,7,8,2,10,12}

}

The limitation above is the size of the unsigned int in the system. If say that size is 32 then the above will only work for sets with cardinality of up to 32. This is a problem that is easy to overcome. Just use bigger integers. For example if you use a compiler that follows the C99 standard then you can include the `<stdint.h>`

header and use `uint64_t`

type instead of the `unsigned int`

to be able to utilize the algorithm for sets with cardinality of up to 64. For bigger sets you would have to use some big integer library or just code it yourself.

Well that’s it. I hope some of you also find this algorithm to be elegant and nice and I wish it has been helpful for you. As always any comments, corrections and feedback are more than welcome. Please use the form below.

Additionally if the post caught your interest and you love C programming in general why not check my work in the Refu Library? It currently needs more contributors and people who are able and willing to provide feedback! You could be one of them 🙂

Nice and well explained algorithm, and it also brings some good memories of my school days. Now I worship the teachers who taught us programming at this level when we were 15.