Tuesday, July 1, 2014


I implemented an efficient algorithm for Anagram assignment, which finds anagrams faster than Odersky wanted by applying SICP coin change algorithm. It should be faster because it does not look up for all permutations since it is obvious that order of coins does not change the sum. The algorthm therefore produces single anagram "aab" or "aba" or "baa" for any of them entered, which means that I want to permute the results. It makes sense first to produce small amount of combinations and then permute them since anagram search space is huge -- it is a dictionary of all english words!

Here is the scala code. Pleas appreciate how multiests, which we actually need, generalize both permutations with and without replacements. Multisets allow you to specify how many different items you have (how many replacements can you make for that item) whereas with replacement permutation hardcodes infinite supply of replacements (so that you can fill all the output string with a single item). Without replacement means that you can use every item only one time in the output string.

No comments: