Powerset Construction Algorithm

0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

The Algorithm

We begin by observing a general trend of numbers in the decimal system as they are converted to binary. Let us consider the upper and lower limits of this experiment to be 0 and 16 ( 2 raised to the power 4 ).

#!/usr/bin/env python
#Convert a number in the decimal system to the binary system
#file: decimaltobinary.py

def converter(i, num_length):
        b = ''
        while i > 0:
                j = i & 1
                b = str(j) + b
                i >>=  1
        bin_list = [ int(x) for x in str(b)]
        reqd_bin_list = [0] * ( num_length - len(bin_list) ) + bin_list
        return reqd_bin_list
 

That snippet uses the most trivial decimal to binary conversion algorithms around and observe that the output is a list whose length is the same as that of the length of the initial set.The idea behind this is to compare elements with the same index, in the set and in the string and use simple True / False to decide which element to pick from the original set to construct one subset. The following example should clear up all doubts:

Let us consider a set {a, b, c, d}. It has 4 elements. Consider the set of binary strings of length two that were shown earlier. If we look at "0000" and compare each element in it to the element in the set having the same index, we have 0s pointing to each element. Hence, no element shall be included. This subset obtained is called the null set.

Let us look at "0001". The first element is 0, hence the first element of the set won't be included, neither will the second and the third. But the 4th element is 1. Hence, the subset we obtain now is {d}. As we proceed through the 4 bit gray code, we find that we get subsets of lengths 0, 1, 2, 3 and 4 (which is the original set itself). Throw all these sets into another set and the result is the powerset. Cool, isn't it?

The final problem we need to tackle involves creating the binary numbers. Observe the following table. It displays the decimal number and adjacent to it, it displayes the binary equivalent:

0       [0, 0, 0, 0]
1       [0, 0, 0, 1]
2       [0, 0, 1, 0]
3       [0, 0, 1, 1]
4       [0, 1, 0, 0]
5       [0, 1, 0, 1]
6       [0, 1, 1, 0]
7       [0, 1, 1, 1]
8       [1, 0, 0, 0]
9       [1, 0, 0, 1]
10      [1, 0, 1, 0]
11      [1, 0, 1, 1]
12      [1, 1, 0, 0]
13      [1, 1, 0, 1]
14      [1, 1, 1, 0]
15      [1, 1, 1, 1]

Once this is done, it is extremely easy to whip up some code that will construct those subsets and finally the powerset and here is a Python implementation:

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
#file: powerset.py

import decimaltobinary

def powerSetMaker(set_name):
        powerset = []
        for i in range(2 ** (len(set_name))):
                bin_list = decimaltobinary.converter(i, len(set_name))
                subset = []
                for n in range(len(bin_list)):
                        if bin_list[n] == 1:
                                subset.append(set_name[n])
                        else:
                                continue
                powerset.append(subset)
        return powerset

The following snippet of Python code will help up throw the subsets into a file named output.txt line by line:

f = open("output.txt", "w")
f.writelines(str(x) + "\n" for x in powerSetMaker(set_name))
f.close()

Consider a set [1, 2, 3, 4, 5]. here are 5 elements and hence there are going to be 32 (two raised to the power 5) subsets. Now, if we run the above code to figure out the subsets, this is what output.txt looks like:

[]
[5]
[4]
[4, 5]
[3]
[3, 5]
[3, 4]
[3, 4, 5]
[2]
[2, 5]
[2, 4]
[2, 4, 5]
[2, 3]
[2, 3, 5]
[2, 3, 4]
[2, 3, 4, 5]
[1]
[1, 5]
[1, 4]
[1, 4, 5]
[1, 3]
[1, 3, 5]
[1, 3, 4]
[1, 3, 4, 5]
[1, 2]
[1, 2, 5]
[1, 2, 4]
[1, 2, 4, 5]
[1, 2, 3]
[1, 2, 3, 5]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]

So, we have 32 unique subsets there. And we indeed have obtained the powerset. This is how powersets can be easily constructed.

Shriphani Palakodety.

http://shriphani.com/blog/category/python

http://shriphani.com/blog/category/mathematics