Suppose dict
is an array of strings that your dictionary and scrambled
is a scrambled word (a string). Considering all permutations of scrambled
or (far worse) the elements of dist
would be highly inefficient. Suppose, for example, the first two letters of one scrambled permutation were qz
. If there were no element (word) in dict
that begins qz
, there would be no point in considering any of the permutations of scrambled
that begin qz
.
Data Structures
Suppose this were our dictionary.
dict = ["dog", "cat", "cow", "emu", "cod", "cobra"]
If we just want to see if a few scrambled words were in the dictionary, we could do this for each:
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
The more interesting question is how to do this in a more efficient way, for checking large numbers of posssilby-longish words that have many permutations.
The first step is to reorganize the dictionary to make lookups for efficient. I am not the best person to suggest how that be done, as I am not familiar with that (or any other) branch of computer science. Here is one way, using a multi-level hash:
dh = { "c"=>{ "a"=>{ "t"=>nil },
"o"=>{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil } },
"d"=>{ "o"=>{ "g"=>nil } },
"e"=>{ "m"=>{ "u"=>nil } } }
dh["c"]
"contains" all words that begin with "c"; dh["c"]["a"]
contains all words that begin with "ca", and so on. dh["c"]["a"]["t"] => nil
signifies that dh["c"]["a"]["t"].join('') => 'cat'
is one of the words in the dictionary. I will assume that you have dh
. If you would like suggestions on how to construct dh
from dict
, perhaps you could ask that as a separate question.
Code
Here is a (recursive) method that could be used to see if any of the unscramblings of scrambled
are contained in dict
. (It would not be difficult to modify this to compile a list of all permutations that are found in dict
, but that is not the problem I've addressed.) This method is called with 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
Example
look_up(dh, "owc") #=> "cow"
look_up(dh, "mue") #=> "emu"
look_up(dh, "bocar") #=> "cobra"
look_up(dh, "esuomhcruhc") #=> nil
Explanation
Suppose dh
is as above and scrambled => "owc"
. Then
left = "owc"
used = ''
left.size #=> 3
enum = left.size.times #=> #<Enumerator: 3:times>
We can convert enum
to an array to see what it will be passing to its block:
enum.to_a #=> [0, 1, 2]
Initially, the block variable i
is set to 0
and
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
, combined with left_copy.empty? => false
, means there are no words in the dictionary beginning with 'o', so we return to the top of the loop and set i => 1
and consider words beginning with '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
There are no words in the dictionary beginning with 'w'
, so we loop again with 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}}
This shows that there are words in the dictionary beginning 'ca`` and
'co'`.
As v
is a hash, we call the method recursively
word = look_up(v, left_copy, used + e)
# look_up({"a"=>{"t"=>nil},
# "o"=>{"b"=>{"r"=>{"a"=>nil}}, "w"=>nil, "d"=>nil}},
# "ow",
# "c")
Calculations proceed similarly for additional letters. When it is found that there are words in the dictionary for the string "co"
represented by:
{ "b"=>{ "r"=>{ "a"=>nil } }, "w"=>nil, "d"=>nil }
we conclude that, since this hash contains "w"=>nil
, that "cow"
is in the dictionary, so we return 'cow'
up the recursive chain and are finished.