## 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.

Pages: 1 2

### 10 Responses to “Anagrams”

1. FalconNL said

```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) d
```

Largest anagram class in my dictionary: ["pares","parse","pears","rapes","reaps","spare","spear"]

2. g said

python:

```
wordlist = [line.strip() for line in open("WORD.LST")]
dic = {}
for word in wordlist:

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)
```
3. [...] 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 [...]

4. kryptosfan said

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!

5. Abhijith said
```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"]

6. Abhijith said

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}"
```
7. [...] From an anagrams programming page: [...]

8. [...] Phil from Programming Praxis had posted this problem in his post. You can also find the implementation in different languages. Share/BookmarkRelated [...]

9. [...] 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. [...]

10. Vikas Tandi said

Here is my implementation in C