Ever needed to find all k-combinations of a set? Of course! I’m pretty sure everybody has run into this problem one way or another, as part of your development work, a combinatorics assignment (eek!) or in every day life. For me, I needed to implement this for generating association rules. What better way to prototype my eventual Java implementation than to use Groovy.
def choose(def itemset, int choose) { def choose(def itemset, int choose) { def results = [] //Initialize indices int[] indices = new int[choose] for (i in 0..<choose) { indices[i] = i } boolean hasMore = true; while (hasMore) { def combo = [] for (i in 0..<indices.size()) { combo << itemset[indices[i]] } results << combo hasMore = { /* Closure to move the right-most index */ int rightMostIndex = { /* Closure to find the right-most index */ for (i in choose-1..0){ int bounds = itemset.size() - choose + i if (indices[i] < bounds) return i } return -1 }() // execute closure // increment all indices if (rightMostIndex >= 0) { indices[rightMostIndex]++ for (i in rightMostIndex+1..<choose) { indices[i] = indices[i-1] + 1; } // there are still more combinations return true } // reached the end, no more combinations return false }() // execute closure } return results }
I’ve based my implementation off one from Applied Combinatorics by Alan Tucker. First, there is an indice array that stores the k positions in the itemset. The items at these index locations are the k-combinations. The algorithm increases the right-most index until it reaches the last element of the itemset, then increases, the second right-most index and so on.
I wouldn’t recommend this implementation when dealing with large itemsets. A deficiency with this one-method approach is that a single list is constructed containing all of the combinations. This list can grow to be very large, very fast. It can be easily adapted to provide one combination at a time by refactoring the hasMore check into a separate method. This way, it would act like an iterator. It’s too bad that Groovy doesn’t have support for the do-while loop as well, otherwise the hasMore closure could have been factored out into a really cool while check.
