I recently needed to write a Combinatorial Iterator for a project I’m working on. That is a class which when given a size and a collection of items (normally a set), returns all the possible unique combinations of elements from the collection of the given size. For instance the combinations of size 3 of the set [1,2,3,4] are [1,2,3], [1,2,4], [1,3,4] and [2,3,4]. There is a nice discussion of this problem on StackOverflow. The number of possible combinations can explode in size quickly, there are 2,598,960 combinations of five cards from a standard pack of 52 cards. Thus I wanted to handle each combination in turn as required, rather than calculate all combinations upfront. Having recently started learning Scala and Ruby, I decided to implement my solution in those languages, plus Java (which I use every day at work).
My first solution was in Java and shown below. I haven’t ensured
thread-safety (or for the other language examples) as I don’t presently
need it in my single threaded application. I have omitted the comments
to keep the size down (similarly test classes are not shown). It works
by storing the indices into the element list of the next combination to
return with a call to
next(). Then after constructing the combination,
the indices are incremented (
incrementIndices()) by finding the next
index to increase and then setting the indices after this to be one
higher than the one before. With a bit of testing, this was the fastest
version I found (which is why I use
indices != null as the end
condition - it was a little faster).
In an unscientific test, this chose combinations of 5 from 50 elements
in around half a second, and 5 from 100 in 18 seconds on my old, slow
laptop. The first thing to notice is that to use the class easily in
Java I implemented the
Iterable interfaces. This allows
me to do things like:
However, there is quite a bit of code to do not much. Implementing
remove() just to throw an exception is a little pointless and
annoying. So I reimplemented the algorithm in Scala similarly
implementing the language’s
Iterator trait. Below is my second
This version is not particularly functional. My first version did the
incrementIndex in far fewer lines (shown below - there are probably
even better ways), but the result was an order of magnitude slower.
In order to get roughly Java equivalent performance I had to write it in a Java-like manner. Scala does not use lazy evaluation like Haskell. So when performing operations on a list, all the elements of a list are used. Instead I had to mimic a Java loop break, which doesn’t exist in Scala. Also lists are immutable, so I had to use arrays to allow in-place updating in order to prevent the creation of many superfluous lists. This chose combinations of 5 from 50 elements in around two seconds, and 5 from 100 in 83 seconds.
I also wrote two Ruby versions. Ruby doesn’t have an iterator interface, so I created a not-so-nice translation of the Java version for comparison purposes (a better version is shown later). It took 35 seconds to choose 5 from 50 so I didn’t even bother trying the larger test.
However, that’s not fair on Ruby because the generally accepted way of
implementing iterator functionality in the language is to pass a block
to a function which
yield’s for each element of the iterator. A much
nicer Ruby version using this paradigm is below.
Which is exercised with:
This more natural Ruby version took a more respectable (but still slow)
15 seconds to chose 5 from 50. It is not as flexible as the Java-like
implementation, one couldn’t for instance stop at an arbitrary point in
the iteration. Although, it does win the beautiful code competition. A
similarly elegant Scala version should be possible at the expense of
either: creating a version similar to the Ruby above and giving up the
Iterator trait and (and thus the extra functionality it provides - see
later); or, using list functions and becoming roughly the same speed as
the Ruby version.
A version like the Ruby one above, while technically possible in Java,
would be a mess due to the lack of closures and the need to create an
interface to handle the code blocks to which to yield. Best not to think
about it. It would be fairly easy to write a similar Scala version, but
completely unnecessary. The Scala
Iterator trait provides a number of
methods that allow you to map, fold, filter, and more over the iteration
elements just by implementing
next. So to get the number
of items in the iterator you could iterate using these functions:
Or, using the built in for loop:
Which can be abbreviated as:
Plus many other succinct and powerful operations. Very nice.
In my opinion the results of this exercise are:
Ruby and Scala are definitely more elegant - Java has become a business language. This is not a particular problem, but its age and need to satisfy many stakeholders mean that a lot of cruft has been added to the language (does anyone know all the API well?). At the same time powerful ideas have become common in newer languages, but the same need to accommodate existing stakeholders and avoid non-backward compatible changes means Java has trouble adding them. Not to say I’m going to stop using Java or recommend others do so. It is still the best tool for many tasks, and it or the similar C# are rightly the default choices for large companies (maybe not small firms, but definitely the large firms/projects I tend to work on commercially). Just that Java has provided me with good jobs for 12 years now, but it’s showing its age and may not be doing the same in another 12 years. I can see myself coding for fun increasingly in other languages.
I have no insight or preference as to what could replace Java. I would say that at present neither Ruby or Scala are mature enough to use as a drop-in replacement. However, in time they could easily be good enough. I remember using Java soon after it was introduced in 1997 and all the same arguments used against the newer languages versus Java (slow, lack of tools/libraries, not enough people know it) were also used against Java versus the then dominant C++. Time changes many things.
Comments: I have removed the commenting system (for privacy concerns), below are the comments that were left on this post before doing so…
Joseph @ 2010-06-05 - Cool, thank you for sharing. I still wonder why no math library (commons, jdk etc.) hasn’t implemented anything for combinations… If you have an iterator generating combinations where the order matters (“a, b, c” “c, b, a”) please let me now. Your solution is pretty quick, I tried to modify it but it was a dead end… Best Regards, Joseph
Joseph @ 2010-06-05 - Got it…the incrementIndices algorithm needed more attention :-)