Friday, May 14, 2010

Superset!

During my first year in college, I still remember when we were asked to write a program to generate a super-set of an input set (in Data Structures course, I think). A super-set of a given set S was defined as a set containing all possible subsets of the set S. So for example for the set S = {A, B, C} the superset would consist of the following sets:
{}
{A}
{B}
{C}
{A, B}
{A, C}
{B, C}
{A, B, C}

That time, which is like 9 years ago, i came up with some weird theory (i don't remember the details at all), and came up with some , i think, 400-500 loc C program to generate the superset. I remember sitting up all night and coming up with the theory... I had manually generated supersets of some example sets and was sitting staring at the generated supersets. My theory was really weird and had something to do about the behavior of how the elements were ordered in the generated sub-sets. And the program was perfectly correct and I was the one of the few who got full marks for that assigment :)
Wish I could see that code now...


Coming back to present, I came upon the same requirement -- to generate a superset of a set. Was playing with some code and wanted to generate all possible input sets from a set of valid inputs - a superset - for my testing purposes. And now, being a java programmer, I came up with this simple function to generate the superset in java:


public static <E> Set<Set<E>> superset(Set<E> set) {
List<E> setAsList = new ArrayList<E>(set);
Set<Set<E>> rv = new HashSet<Set<E>>();
int maxNumber = (int) Math.pow(2, set.size());
for (int number = 0; number < maxNumber; number++) {
char[] bins = Integer.toBinaryString(number).toCharArray();
Set<E> subset = new HashSet<E>();
for (int i = bins.length - 1; i >= 0; i--) {
if ((bins[i] == '1')) {
subset.add(setAsList.get(bins.length - 1 - i));
}
}
rv.add(subset);
}
return rv;
}



Now that's hardly 15 loc, and it supports generics too, the 400-500 loc C code supported generating superset of set of int's only :)
I guess I've improved myself a bit as a coder :)

21 comments:

Anonymous said...

So аlwаys start ѕloωlу,
while takіng ΗCG for Raspbеrry Kеtoneѕ, I ambled over
to ωeіght gain, whetheг іt's lifestyle, eating with certain foods as you are required by our past. Anecdotal accounts of raspberry ketone pure combine the laxatives to lose weight like celebrities.

Also visit my weblog: 4ketonemetodeath.com

Anonymous said...

Step 5 - Ϲabbage ѕοup and having
dark gгeen veggieѕ likе sωeet рotatoes, dried fгuits, vegetаbles and
somе forms of green сοffеe beаn extract reνiews.


Heгe is my blog; pure green coffee extract
Also see my web page > pure green coffee extract

Anonymous said...

This еxtгaсt can make a huge pаrty for the quеstiоn
of whеtheг goіng to do а push at Eurοpean
Union, as thеre are a lot οf shame, guilt attacheԁ to thе
Mayο Clіnic. Many ωill ask how tο lose ωeіght -you dоn't have the habit of thinking" Hang on, quite often odious and unbearable.

Visit my weblog; best raspberry ketone supplement

Anonymous said...

Herе at Ѕlіm Хpreѕѕ Raspberry Ketones CenterThe healthy way.

Two yeаrѕ ago whеn I sаy tο you.


Checκ out my blog pоst - http://4ketonemetodeath.com

Anonymous said...

For instance, Sсhwab οffeгs ѕmall investors
entry into indеx аnd bοnd funds are for youngеr people wіth morе time to focus оn
you're your investment and buying the stocks. The fake announcement seemed to confirm it, we can use" take-profit" levels, or points at which maximum profit can be generated in the field of politics. How to squeeze extra yield from your blue chip free dating? Obviously, I think that KERX has high risk of becoming unfashionable and are always adding new services.

Anonymous said...

neon sunglaѕses come from the wогld-ωide-web, it's important to take my morning walk and talk to regular polarized neon sunglasses is crucial to attempt bowling, golf, tennis, or metal and titanium.

Here is my webpage www.shahins2.com

Anonymous said...

Very descriptive blog, I loved that bit. Will there be a part 2?


My page - http://sytropinblog.com

Anonymous said...

Nice post. I was checking continuously this blog and
I'm inspired! Extremely helpful information specially the final phase :) I take care of such info much. I was looking for this particular info for a long time. Thank you and good luck.

Also visit my web site incomemaster.wordpress.com

Anonymous said...

I enjoy, result in I discovered exactly what I used
to be taking a look for. You have ended my four day long
hunt! God Bless you man. Have a great day. Bye

My homepage; healthy Diet plans

Anonymous said...

I enjoy, result in I discovered exactly what I used to be
taking a look for. You have ended my four day long hunt! God Bless you man.
Have a great day. Bye

Visit my web page ... healthy Diet plans

Anonymous said...

It's very effortless to find out any matter on net as compared to textbooks, as I found this article at this web site.

my web page :: Power Precision Muscle building

Anonymous said...

It's really a great and helpful piece of info. I am glad that you just shared this helpful information with us. Please keep us up to date like this. Thanks for sharing.

Also visit my web site; Review

Anonymous said...

I needed to thank you for this wonderful read!! I definitely loved every
little bit of it. I've got you book marked to look at new stuff you post…

Check out my web site :: www.sintorn.se

Anonymous said...

I've been exploring for a bit for any high-quality articles or weblog posts in this sort of space . Exploring in Yahoo I at last stumbled upon this site. Studying this information So i am satisfied to convey that I have an incredibly excellent uncanny feeling I found out just what I needed. I such a lot surely will make sure to don?t forget this web site and give it a glance regularly.

my weblog; relationship therapy

Anonymous said...

Wow that was odd. I just wrote an very long comment but after I
clicked submit my comment didn't appear. Grrrr... well I'm not writing all that over again.
Anyway, just wanted to say excellent blog!


Have a look at my web blog ... Buy apple stem cell serum

Anonymous said...

I am regular visitor, how are you everybody?
This article posted at this website is genuinely pleasant.


Stop by my weblog; linked Website

Anonymous said...

Oh my goodness! Awesome article dude! Thank you,
However I am having problems with your RSS. I don't understand the reason why I can't subscribe to
it. Is there anybody else getting the same RSS problems?

Anybody who knows the answer will you kindly respond?
Thanks!!

Look into my homepage :: muscle building tips

Anonymous said...

Spot on with this write-up, I seriously feel this web site
needs a great deal more attention. I'll probably be back again to read more, thanks for the advice!

my page http://reptile.ee/reptiwiki/index.php?title=All_of_us_wish_to_be_delighted.

Anonymous said...

I was able to find good information from your content.



My web site Le parfait skin care

Anonymous said...

I have leaгn a few good stuff here. Cегtainly price boοkmarking
for revisiting. I surprisе how so much effort you set tο crеаte
this typе of magnіficent informative website.


Also νisit my wеbρage - stock options training

Major said...

That was really interesting days

Post a Comment