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 "_".
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
}
# Examples:
catch {console show}
puts [anagram anyof RETAINS]
puts [anagram template RETAINS *A]
puts [anagram template TO_UE ?????]Alastair Davies - 17 January 2006
KPV By far the fastest way to do this is to preprocess the word list and create what's known as an anagram dictionary[L3 ]. Once that's done, figuring out anagrams takes O(1) time.
HJG I get the error 'Invalid command name "wordList"'. Maybe a Tcl 8.5 feature ? - RS No - looks like a function that reads the word list file, and returns them as a list. Left as an exercise for the reader :^)
ALD: HJG will need to download [L4 ] the source code that defines "wordList". The start and end of this look like:
proc wordList {{lang en}} {
switch $lang {
en {
return {
AARDVARK
AARDVARKS
ABACI
ABACK
ABACUS
ZYGOTE
ZYGOTES
ZYGOTIC
ZYMURGY
}
}
}
}