Anagrams
April 10, 2009
Our solution reads each word in the dictionary, “signs” the word by sorting its letters, and stores it in a hash table with other words that have the same signature. On request, the anagrams of an input word are determined by signing the input word and looking up its anagrams in the hash table. Here we compute the signature:
(define (sign word) (list->string (sort char<? (string->list word))))
Here we define the hash table and read the dictionary. The update function conses the new word onto an existing list of words with the same signature, or begins a new list if none exists:
(define anagrams (make-hash string-hash string=? '() 99991))
(with-input-from-file "/usr/dict/words"
(lambda ()
(do ((word (read-line) (read-line))) ((eof-object? word))
(let ((key (sign word)))
(anagrams 'update key (lambda (k v) (cons word v)) (list word))))))
Looking up the anagrams of a word is simple:
(define (anagram word) (anagrams 'lookup (sign word)))
The local dictionary doesn’t store plurals, so it finds only three anagrams for post:
> (anagram "post")
("stop" "spot" "post")
To find the largest anagram class, we sort by class size in descending order:
(define (by-class-size-desc a b)
(let ((a-size (length (cddr a)))
(b-size (length (cddr b))))
(> a-size b-size)))
> (cdar (sort by-class-size-desc (anagrams 'enlist)))
("trace" "crate" "cater" "carte" "caret")
Other dictionaries find larger anagram classes.
Our solution uses make-hash, string-hash, sort and read-line from the Standard Prelude. You can see the solution at http://programmingpraxis.codepad.org/b5C4nEf9.
Programming Praxis 
In Haskell:
import Data.List import GHC.Exts import Control.Arrow import Data.Map (Map, findWithDefault, fromList) main = do words' <- fmap lines $ readFile "words.txt" print . last . sortWith length $ map (anagrams (anagramMap words')) words' anagramMap :: [String] -> Map String [String] anagramMap = fromList . map (sort . head &&& id) . groupWith sort anagrams :: Map String [String] -> String -> [String] anagrams d s = findWithDefault [] (sort s) dLargest anagram class in my dictionary: [“pares”,”parse”,”pears”,”rapes”,”reaps”,”spare”,”spear”]
python:
wordlist = [line.strip() for line in open("WORD.LST")] dic = {} for word in wordlist: dic.setdefault(len(word), set()).add(word) def find_anagrams(str): anagrams = () if len(str) in dic: for word in dic[len(str)]: match = True for letter in frozenset(str): if str.count(letter) != word.count(letter): match = False break if match: anagrams += word, return anagrams def longest_anagram(): anagrams = () for key in dic: anagrams += tuple(find_anagrams(word) for word in dic[key]) return max(anagrams, key=len)[…] we have used in several exercises (Mark V. Shaney, Word Frequencies, Dodgson’s Doublets, Anagrams). Hash tables are often used as the underlying implementation for dictionaries, and in a previous […]
I’m not much of a programmer but if we can look past that character deficit…
Anyways, I’m looking at the puzzle sculpture Kryptos and think the keywords can be retrieved from the Morse Code messages via anagramming. I’m trying to recruit help from folks with an interest in anagrams across WordPress. I kept the details brief because it’s all available online. Besides help, I was wondering if there are anagram methods that work in an algorithmic method allowing you to systematically build a second plaintext message from the original. I may be grasping at straws here but I was hoping you and maybe your readers might have some direction for me as I feel rather lost. Thanks!
def anagram(file) table = [] File.open(file).each_line do |word| # assumes one word per line unsorted = word.chomp # get rid of \n sorted = unsorted.split("").sort.join("") if table.has_key?(sorted) table[sorted].push(unsorted) else table[sorted] = [].push(unsorted) end end table end def longest_anagram_class(hash) hash.sort_by { |k, v| -1 * v.length }.first.last end h = anagram("/usr/share/dict/words") puts "Longest anagram class #{longest_anagram_class(h).inspect}"output:
=> Longest anagram class [“angor”, “argon”, “goran”, “grano”, “groan”, “nagor”, “orang”, “organ”, “rogan”]
Improved version and shorter version.
def anagram(file) table = Hash.new { |hash, key| hash[key] = [] } File.open(file).each_line do |word| # assumes one word per line unsorted = word.chomp # get rid of \n sorted = unsorted.split("").sort.join("") table[sorted].push(unsorted) end table end def longest_anagram_class(hash) hash.sort_by { |k, v| -1 * v.length }.first.last end h = anagram("/usr/share/dict/words") puts "Longest anagram class #{longest_anagram_class(h).inspect}"[…] From an anagrams programming page: […]
[…] Phil from Programming Praxis had posted this problem in his post. You can also find the implementation in different languages. Share/BookmarkRelated […]
[…] Anagrams Words that are formed from the same set of letters are anagrams of each other. For instance, pots, post, stop, spot, opts, and tops are anagrams. Your task is to write a program that, given a dictionary and an input word, prints all the anagrams of the input word. You are also to determine the largest anagram class in your dictionary. […]
Here is my implementation in C
http://codepad.org/Xx6GE4vU
https://github.com/ftt/programming-praxis/blob/master/20090410-anagrams/anagrams.py