anagram.fs

/// <summary>
///   Builds a map where the keys are word signatures and
///   each value is the list of words that share that signature.
///   The signature of a word is simply a string containing
///   the word's letters, sorted. Thus "dog" and "god" will
///   both have the signature "dgo", and the entry in the map
///   with that key will be those two words.
///
///   This let's us quickly find anagrams
/// </summary>
module AnagramMap =
        
    /// Turns a string into a string where all the characters are sorted
    let private signatureOf (word:string) =
        word.ToLower()
        |> Seq.sort
        |> System.String.Concat

    ///  Builds an anagram map from a string sequence
    let buildDictionary wordList =
        seq {
            for (signature, words) in Seq.groupBy signatureOf wordList do
                yield (signature, Set.ofSeq words)
        } |> Map.ofSeq

    ///  Finds the set of all anagrams in a map
    let anagramsOf word anagrams =
        anagrams
        |> Map.tryFind (signatureOf word) 
        |> Option.defaultValue Set.empty