Elegant Power Set Calculation Algorithm

A very easy to understand and elegant algorithm to calculate the powerset of a given set of numbers. It is based on the properties of binary numbers. An example in C code along with explanation is provided.

Binary Power Set Representation

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 2s 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? 2s-1 = 23-1 = 7. In binary seven is 111 as we can see from the figure below.

Binary representation of 7
Binary representation of 7

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.

Binary Power Set Representation
Binary Power Set Representation

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 🙂

1 thought on “Elegant Power Set Calculation Algorithm”

  1. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.