Computers fail again. The TSX halted its trading for an entire day due to problems with its data feeds. What sort of problem with data feeds could be so horrible to require an entire day to fix? Source.
Monthly Archive for December, 2008
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.
Markers are a great feature of Eclipse and there are some great articles on creating Markers. However, I couldn’t find a good article on opening markers in an editor. So, here’s the best call sequence that I could figure out:
IJavaElement element = ...; IEditorInput input = EditorUtility.getEditorInput(element); IEditorPart editor = getSite().getPage().openEditor(input, (input instanceof FileEditorInput) ? : JavaUI.ID_CU_EDITOR : JavaUI.ID_CF_EDITOR); IDE.gotoMarker(editor, sNode.getMarker());
EditorUtility is an internal JDT class, but I couldn’t find a better way of doing this. A check on the return type of the getEditorInput call is necessary to since it can return either a file editor (for compilation units) or a class file editor.
