ruby to unjumble words
我正在尝试编写一个ruby脚本，解读置换的单词，生成所有排列，并在txt目录中搜索单词。 我遇到了问题。
这是我所拥有的简单概述。
print "Enter Permuted Word:" words = STDIN.gets.chomp a = to_array(s) print a, "\n" perms = a.permutation(3).to_a.collect do |perm| perm.join end print perms, "\n" file = file.open("words.txt", "r") file.read.each_line do |line| fields = line.chomp.split(",") words_un = fields[1] end file.close txt文件看起来像这样
words_un Aarhus Aaron Ababa aback abaft abandon abandoned abandoning abandonment abandons abase ... Zulus Zurich
假设dict是一个字符串数组，你的字典scrambled是一个乱码字（一个字符串）。 考虑到scrambled所有排列或者（更糟糕的是） dist的元素将是非常低效的。 例如，假设一个扰乱排列的前两个字母是qz 。 如果dict中没有元素（单词）开始qz ，那么考虑任何开始qz的scrambled排列都没qz 。
数据结构
假设这是我们的字典。
dict = ["dog", "cat", "cow", "emu", "cod", "cobra"]
如果我们只想查看字典中是否有一些混乱的单词，我们可以为每个单词执行此操作：
r = 'mue'.split('').permutation(3).find { |w| dict.include?(w.join) } #=> ["e", "m", "u"] r.any? ? r.join('') : nil #=> "emu" r = 'nvwls'.split('').permutation(3).find { |w| dict.include?(w.join) } #=> nil
更有趣的问题是如何以更有效的方式执行此操作，以检查具有许多排列的大量posssilby-longish单词。
第一步是重新组织字典以使查找有效。 我并不是建议如何做的最好的人，因为我不熟悉那个（或任何其他）计算机科学的分支。 这是一种使用多级哈希的方法：
dh = { "c"=>{ "a"=>{ "t"=>nil }, "o"=>{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil } }, "d"=>{ "o"=>{ "g"=>nil } }, "e"=>{ "m"=>{ "u"=>nil } } }
dh["c"] “包含”所有以“c”开头的单词; dh["c"]["a"]包含以“ca”开头的所有单词，依此类推。 dh["c"]["a"]["t"] => nil表示dh["c"]["a"]["t"].join('') => 'cat'是1字典中的单词。 我会假设你有dh 。 如果您想了解如何从dict构造dh建议，也许您可以将其作为一个单独的问题。
码
这是一个（递归）方法，可用于查看dict是否包含任何scrambled的unscramblings。 （修改它以编译在dict中找到的所有排列的列表并不困难，但这不是我已解决的问题。）使用look_up(dh, scrambled)调用此方法。
def look_up(dh, left, used = '') left.size.times do |i| left_copy = left.dup e = left_copy[i] left_copy[i] = '' v = dh[e] case v when nil (return used + e) if left_copy.empty? when Hash word = look_up(v, left_copy, used + e) return word if word end end nil end
例
look_up(dh, "owc") #=> "cow" look_up(dh, "mue") #=> "emu" look_up(dh, "bocar") #=> "cobra" look_up(dh, "esuomhcruhc") #=> nil
说明
假设dh如上所述并且scrambled => "owc" 。 然后
left = "owc" used = '' left.size #=> 3 enum = left.size.times #=> #
我们可以将enum转换为数组，以查看它将传递给它的块：
enum.to_a #=> [0, 1, 2]
最初，块变量i设置为0和
left_copy = left.dup #=> "owc" e = left_copy[i] #=> left_copy[0] => "o" left_copy[i] = '' #left_copy[i] = '' left_copy #=> "wc" v = dh[e] #=> v = dh[0] => nil
dh[0] => nil ，与left_copy.empty? => false结合使用left_copy.empty? => false left_copy.empty? => false ，表示字典中没有以’o’开头的单词，所以我们返回循环的顶部并设置i => 1并考虑以'o'开头的单词：
left_copy = left.dup #=> "owc" e = left_copy[i] #=> left_copy[1] => "w" left_copy[i] = '' #=> left_copy[1] = '' left_copy #=> "oc" v = dh[e] #=> v = dh[1] => nil
字典中没有以'w'开头的单词，所以我们再次循环使用i => 2 ，
searching for words in the dictionary beginning with `'c'`: e = left_copy[2] #=> "c" left_copy[2] = '' #=> left_copy[2] = '' left_copy #=> "ow" v = dh[2] #=> {"a"=>{"t"=>nil}, # "o"=>{"b"=>{"r"=>{"a"=>nil}}, "w"=>nil, "d"=>nil}}
这表明字典中的单词以'ca`` and ‘co’开头。
由于v是哈希，我们递归地调用该方法
word = look_up(v, left_copy, used + e) # look_up({"a"=>{"t"=>nil}, # "o"=>{"b"=>{"r"=>{"a"=>nil}}, "w"=>nil, "d"=>nil}}, # "ow", # "c")
对于其他字母，计算也类似地进行。 当发现字典中有字词"co"表示时：
{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil }
我们得出结论，由于这个哈希包含"w"=>nil ，所以"cow"在字典中，所以我们将'cow'返回到递归链并完成。