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.

About these ads

Pages: 1 2

11 Responses to “Anagrams”

  1. FalconNL said

    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) 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:
        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)
    
  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

    http://codepad.org/Xx6GE4vU

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: