[Assuming you can reuse the source letters within one word]: For each word in your dictionary list, construct two arrays of letters - one for the candidate word and one for the input string. Subtract the input array-of-letters from the word array-of-letters and if there weren't any letters left over, you've got a match. Code to do that looks like this:
def findWordsWithReplacement(sentence)
out=[]
splitArray=sentence.downcase.split(//)
`cat /usr/share/dict/words`.each{|word|
if (word.strip!.downcase.split(//) - splitArray).empty?
out.push word
end
}
return out
end
You can call that function from the irb debugger like so:
output=findWordsWithReplacement("some input string"); puts output.join(" ")
...or here's a wrapper you could use to call the function interactively from a script:
puts "enter the text."
ARGF.each {|line|
puts "working..."
out=findWordsWithReplacement(line)
puts out.join(" ")
puts "there were #{out.size} words."
}
When running this on a Mac, the output looks like this:
$ ./findwords.rb
enter the text.
Ziegler's Giant Bar
working...
A a aa
aal aalii Aani Ab aba abaiser
abalienate Abantes Abaris abas abase
abaser Abasgi abasia Abassin abatable
abate abater abatis abaze abb Abba
abbas abbasi abbassi abbatial abbess
Abbie Abe abear Abel abele Abelia
Abelian Abelite abelite abeltree
Aberia aberrant aberrate abet abettal
Abie Abies abietate abietene abietin
Abietineae Abiezer Abigail abigail
abigeat abilla abintestate
[....]
Z z
za Zabaean zabeta Zabian zabra zabti
zabtie zag zain Zan zanella zant zante
Zanzalian zanze Zanzibari zar zaratite
zareba zat zati zattare Zea zeal
zealless zeallessness zebra zebrass
Zebrina zebrine zee zein zeist zel
Zelanian Zeltinger Zen Zenaga zenana
zer zest zeta ziara ziarat zibeline
zibet ziega zieger zig zigzag
zigzagger Zilla zing zingel Zingiber
zingiberene Zinnia zinsang Zinzar zira
zirai Zirbanit Zirian Zirianian
Zizania Zizia zizz
there were 6725 words.
That is well over 4500 words, but that's because the Mac word dictionary is pretty large. If you want to reproduce Knuth's results exactly, download and unzip Knuth's dictionary from here: http://www.packetstormsecurity.org/Crackers/wordlists/dictionaries/knuth_words.gz and replace "/usr/share/dict/words" with the path to wherever you've unpacked the substitute directory. If you did it right you'll get 4514 words, ending in this collection:
zanier zanies zaniness Zanzibar zazen
zeal zebra zebras Zeiss zeitgeist Zen
Zennist zest zestier zeta Ziegler zig
zigging zigzag zigzagging zigzags zing
zingier zings zinnia
I believe that answers the original question.
Alternatively, the questioner/reader might have wanted to list all the words one can construct from a string without reusing any of the input letters. My suggested code to accomplish that works as follows: Copy the candidate word, then for each letter in the input string, destructively remove the first instance of that letter from the copy (using "slice!"). If this process absorbs all the letters, accept that word.
def findWordsNoReplacement(sentence)
out=[]
splitInput=sentence.downcase.split(//)
`cat /usr/share/dict/words`.each{|word|
copy=word.strip!.downcase
splitInput.each {|o| copy.slice!(o) }
out.push word if copy==""
}
return out
end