Shriphani Palakodety

In Pursuit Of Truth and Beauty

Shriphani Palakodety header image 2
← →

One step forward two steps back…

March 31st, 2008 · 6 Comments · Mathematics, python

I am very sorry Stanford – you won’t have the honor to call yourself the breeding place of the next biggest character in the history of Computer Science. I feel extremely sorry to being you this bad news.

Anyway, in a bout of stupidity (induced by an intense feeling to optimize a stupid script of no apparent worth) I ended up rewriting problem 16 on projecteuler.net using memoization. Well, I guess I am going to be a computer scientist right ?

Well, have a look at it:

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

cache = {}
cache[ 2 ** 0] = 1

def cachePopulator():
        for i in range(1, 1001):
                if cache.has_key(2 ** (i – 1)):
                        cache[2 ** i]= 2 * cache[2 ** (i-1)]

cachePopulator()

cachestring = str(cache[2 ** 1000])
cache_string_list = [ int(x) for x in cachestring ]
print sum(cache_string_list)

Next comes a dose of creativity. This is my algorithm to generate the powerset of a given set. A powerset of a set is basically the set whose elements are subsets of a given set. Now, if the cardinal number of a set is “n”, then it should have {2}^{n} subsets. How? Simple combinatrics.

Subsets can be considered as selections. From a set of n elements, we end up selecting 0, 1, 2 ….. n elements. Hence we have something of the form:

{^n}C{_0}} + {^n}C{_1} + {^n}C{_2} + .......... + {^n}C{_n} = 2{^n}

Now, how do we obtain the powerset of a given set ? I came up with an idea to use binary numbers to get to the answer. Consider that we have a set composed of elements a, b and c.
S =<br /> \begin{Bmatrix}<br /> a, b, c &<br /> \end{Bmatrix}

Let i be allowed to increment from 0 to {2}^{n}. Now observe the magic of the binary system:

i binary Element(s)
0 000 -
1 001 c
2 010 b

and so on. So, depending on the location of 1 in the binary number, we accordingly pick an element from the set and get to the solution. Well, here is the code needed to generate a list containing the digits of the corresponding binary number as over here we need to obtain the indices of 1.

#!/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 &amp; 1
                b = str(j) + b
                i >>=  1
        bin_string = [ int(x) for x in str(b)]
        reqd_bin_string = [0] * ( num_length – len(bin_string) ) + bin_string
        return reqd_bin_string

Then comes the code to generate the powerset:

#!/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
 

You can download the Decimal to Binary converter here. The powerset constructor can be downloaded here.

That should do it :)

Ah right, owing to the mess my life has become ( getting shafted by colleges everywhere ) I have been incapable of responding to comments. I apologize and promise that I will get to making this blog the best in the world soon :)

HAPPY CODING !

Tags:

6 Comments so far ↓

Leave a Comment