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:
#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 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:
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.
Let i be allowed to increment from 0 to . 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.
#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_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:
#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 !

Thanks and great work…..
nice work…..
carry on…
Create con Folder in Windows » Blog Archive » Powerset Generation Algorithm // Nov 9, 2008 at 2:32 pm
[...] also be used to generate all possible combination of string and after doing some googling I found a blog which tells me about the algorithm to generate powerset. Here I am giving you the code in Java for [...]
hey that’s great..But what if i have a set having elements greater than 32(for a 32 bit machine)
or 64 (for 64 bit machine)??
If its the cardinal number you are talking about, then you need to compute 64! and I’m sure Python is capable of doing that. If you’re stuck with Python 2.5, you could use my fast factorial computation algorithm: http://shriphani.com/scripts/factorial.py
Hello sir,
i am in need of a java code which generates powerset for given set of any size
kindly do the needfull
Thanks and regards
Shilpa.R