Version 1 of Anagrams

Updated 2006-01-17 18:56:54

With a given word list (such as from the 12-dicts [L1 ] project) formatted as a Tcl procedure that returns a list [L2 ], it is interesting to speculate on the fastest procedure for obtaining anagrams of a given set of letters.

The following procedure is my effort. It has some refinements: (1) it takes an optional template, as for string match and (2) it allows for a wildcard character (such as the blank in Scabble or the joker in card games), written as "_".

Example use:

 anagram anyof RETAINS
 anagram template RETAINS *A
 anagram template TO_UE ?????

Code:

 proc anagram {style letters {template *}} {
  set anagrams [list]
  set usingTemplate [string match "template" $style]
  foreach word [wordList] {
    if {$usingTemplate} {
      if {![string match $template $word]} {continue}
    }
    set discard $letters
    set flag true
    for {set i 0} {$i<[string length $word]} {incr i} {
      set match [string first [string index $word $i] $discard] 
      if {$match>-1} {
        set discard [string replace $discard $match $match]
      } else {
        #-- We don't hold the char; but we may have a blank
        set match [string first _ $discard]
        if {$match>-1} {
          #-- We do have a blank, so we use that instead
          set discard [string replace $discard $match $match]
        } else {
          set flag false
          break
        }
      }
    }
    if {$flag} {
      lappend anagrams $word
    }
  }
  return $anagrams
 }

Alastair Davies - 17 January 2006