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 :)