language parallax

Please see pingel.org for PowerSet source code (among other algorithms and data structures)

Example usage:


Set<String> elems = new HashSet<String>();
elems.add(”a”);
elems.add(”b”);
elems.add(”c”);

for( Set<String> set : new PowerSet<String>(elems) ) {
System.out.println(set);
}

I noticed in the logs for pingel.org that a lot of people are finding pages there because of searches for “powerset in java” or similar search strings.

There is indeed an implementation of a powerset, and you’re welcome to use it. There are also implementations of CrossProduct, Permuter, DirectedGraph, and UndirectedGraph. I believe those all work as you would expect. (Please tell me if they don’t.)

These were all the result of me looking for optimizations of some Bayesian Network code that I was developing last year. The switch to using Java 5’s generics practically begged me to implement these basic mathematical concepts. I haven’t touched the code in a while, but quickly looking at it convinces me that these are reasonable interfaces and implementations of these ideas. There are definitely some design tradeoffs, though. Especially in the graph objects. It was my first foray into java’s generics, so some of it may be a little unsophisticated.

One thing to note: my implementation of Combiner is not complete. I spent a few hours thinking about this one before I realized it was non-trivial to create an efficient iterator through the combinations of a set. Turns out Don Knuth has devoted a few chapters in his books to this very algorithm. If anyone has the code on hand and can adapt it to the existing interface, I’d love to see it!