How to find an array of all the words in json that can be made by rearranging these letters(Ruby)

Instead of creating all permutations for various inputs, you could also group the words from the dictionary by sorting their letters:

def sorted(str)
  str.chars.sort.join
end

# assume this was read from the JSON file
dict = %w[ab ba abc acb bac bca cab cba]

lookup_hash = dict.group_by { |word| sorted(word) }
#=> {
#     "ab"  => ["ab", "ba"],
#     "abc" => ["abc", "acb", "bac", "bca", "cab", "cba"]
#   }

Although this calculation can be quite expensive for larger dictionaries, you only have to do it once. (you could even store the hash to disk and only update when your dictionary changes)

After creating the hash, it's almost trivial to find the permutations. You just have to fetch the values for the sorted input:

input = gets.chomp
puts lookup_hash[sorted(input)]

This will be much faster than generating all permutation each time.

In Ruby there is already Array#permutation that you can use to calculate all possible words.

letters = "ab" # example
permutations = letters.split(//).permutation.map(&:join)
#=> ["ab", "ba"]

And then there is 'Array#&' that returns only elements from an array that are present in another array.

words = ["ab", "ba", "abc", "acb", "bac", "bca", "cab", "cba"]
words & permutations
#=> ["ab", "ba"]

And you can use JSON.load(File.open('dictionary.json')) to load the JSON file into a Ruby array – as Schwern already wrote in his comment.

Now let's combine all these methods into one class

require 'json'

class LetterLocater
  attr_reader :words

  def initialize(dictionary)
    @words = JSON.load(File.open('dictionary.json'))
  end

  def permutation(letters)
    permutations = letters.split(//).permutation.map(&:join)
    words & permutations
  end
end

ll = LetterLocater.new('dictionary.json')

ll.permutation('ab')
#=> ["ab", "ba"]
ll.permutation('abc')
#=> ["abc", "acb", "bac", "bca", "cab", "cba"]

def find_permutations_in_array(arr, str)
  chars = str.chars.sort
  arr.inject([]) do |res, word|
    res << word if word.size == str.size && word.chars.sort == chars
    res
  end
end

Assumption

I have assumed that the task is one-off, in the sense that the task is to be performed for a single word and a given dictionary, not for possibly many words and the same dictionary.

Approach

I propose that three tests be used to determine if each dictionary word is formed by permuting the letters in the given word:

• reject the dictionary word if its length differs from that of the given word
• if the above test fails, reject the dictionary word if it begins with a string s where it has been determined that no word beginning with s can be formed by permuting the letters of the given word
• if the above test fails, each character in the dictionary is examined in sequence until a character is found that is not present in the given word or whose count in the dictionary word exceeds the count of the same character in the given word, in which case the dictionary word can be rejected

If none of the above tests succeeds we may conclude that the dictionary word can be formed by permuting the letters of the given word.

Note that, in the third test above, if the dictionary word w was rejected when its character at index i was examined we may conclude that no dictionary word that begins with s = w[0,i] can be formed by permuting the characters of the given word, which is the basis for the second test.

Code

def find_em(word, dict)
  word_len = word.length
  ltr_cnt = word.each_char.tally
  prefix = ''
  dict.select do |w|
    next false if w.length != word_len ||
      (prefix.length > 0 && w.start_with?(prefix))
    prefix = ''
    lc = ltr_cnt.dup
    ltrs_used = 0
    w.each_char do |c|
      prefix << c
      break unless lc.key?(c) && lc[c] > 0
      lc[c] -= 1
      ltrs_used += 1
    end
    if ltrs_used == word_len
      prefix = ''
      true
    else
      false
    end
  end
end

Example

word = "aab"

dict = [
  "aaa", "aab", "ab", "aba", "abb", "aca", "acad", "acb", "acc", 
  "acd", "ace", "ba", "bac", "bca", "bcc", "caa", "cab", "cbb"
]

Being a "dictionary", I assume the words of dict are ordered lexicographically, but if that is not the case the first step is to sort the given array words to produce dict.

find_em(word, dict)
  #=> ["aab", "aba"]

Explanation

For the example just given the method processes each word in the dictionary in as indicated by the following:

"aaa", "aab", "ab", "aba", "abb",  "aca", "acad", "acb", "acc", 
   c     m      s     m       c      n       s      r      r
"acd", "ace", "ba", "bac", "bca", "bcc", "caa", "cab", "cbb"
  r      r      s      n     n      r     n      r      r

• "aaa" is rejected (signified by "c", for "count"), when the third character is examined, because word contains only two "a"'s (which is why "c" is shown under the third "a")
• "aab" is matched (signified by "m") because its letters are a permutation of the letters of word
• "ab" is rejected because the length of the word is not the same as the length of word
• "aba" is matched
• "abb" is rejected when the second "b" is examined because there are too many "b"'s
• "aca" is rejected when "c" is examined because word does not contain "c" (indicated by the "n" under the "c")
• "acad" is rejected because it is the wrong size
• "acb", "acc", "acd", "ace" are all rejected because we know from the processing of "aca" that no words starting with "ac" can match (indicated by "r" for "repeat")
• "ba" is the wrong size
• "bac" is rejected because word does not contain "c"
• "bca" does not begin "bac" so we examine each letter from the start of the word until we find "c", which is not contained in word so we reject the word
• "bcc" is rejected because we know from examining "bca" that no words starting with "bc" can match
• "caa" is rejected because word does not contain "c"
• "cab" and "cbb" are rejected because we know from examining "caa" that no words starting with "c" can match

To better understand details of the calculations one might execute the method after having salted it with puts statements. For example, one might execute the following modification.

def find_em(word, dict)
  word_len = word.length
  ltr_cnt = word.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 }
  prefix = ''
  dict.select do |w|
    puts "w=#{w}, prefix=#{prefix}"
    next false if w.length != word_len ||
      (prefix.length > 0 && w.start_with?(prefix))
    prefix = ''
    lc = ltr_cnt.dup
    ltrs_used = 0
    w.each_char do |c|
      puts "  prefix=#{prefix}, lc=#{lc}"
      prefix << c
      break unless lc.key?(c) && lc[c] > 0
      lc[c] -= 1
      ltrs_used += 1
    end
    puts "  for w = #{w} prefix = #{prefix}"
    if ltrs_used == word_len
      puts "  w = '#{w}' a match"
      prefix = ''
      true
    else
      puts "  w = '#{w} *not* a match"
    false
    end
  end
end

Alternative when word is relatively short

If the number of unique permutations of the letters of word is relatively small we could generate each word that is formed by a unique permutation of the characters in word and then use Array#bsearch to perform a binary search to determine if that word is in the dictionary:

def present?(word, dict)
  dict.bsearch { |w| w >= word } == word
end

word.chars.permutation.map(&:join).uniq.select { |w| present?(w, dict) }
  #=> ["aab", "aba"]