If the dictionary is static what's the point of building a hashtable out of it at runtime? If it's not how do we know this'll work with a different dictionary? I didn't know about Gödel numbering though, that part is cool.

This reminds me fondly of things I used to do for programming contests :)

I think I did an anagram dictionary once. My memory is that I computed the anagrams once ever and made a dictionary file which was a sorted word list and the offset of the next anagram of that word. The sorted letters for each anagram group were also in the same list. Because it was searching for multiple word phrases you just did a search on the subsets of letters left for candidates.

Scrabble dictionaries were the most mind bending I think. I don’t think I wrote anagrams up but this is the scrabble one https://williame.github.io/post/87682811573.html

> that I hadn't seen before (though the history of computing is long and Knuth probably noticed it in 1965).

I love that aside. Probably would make a good T-shirt or bumper sticker, like: "Congrats on that clever algorithm you just came up with! Just remember... the history of computing is long and Knuth probably noticed it in 1965.

Really interesting !

What metric best captures the anagram potential of a given set of letters in a given language? One way to solve this problem I can think of is to enumerate, at least partially, the anagrams that can be formed. Then you can come up with a density : nb_of_valid_anagrams / nb_explored_permutations. Why not. But I bet there are more insightful techniques.