Non-brute force approach to finding permissible English word anagrams I am interested in proposed base R/Python solutions (i.e. without relying on external packages/libraries) to the following problem:


  You have a large dictionary containing millions of valid English
  words. You are given an input “word”, which may or may not be an
  anagram of one or more words in the dictionary. Find all possible
  valid words in the dictionary of which the input may be an anagram.
  Note, the input “word” may be meaningless. For example,
  
  input: lloeh output: hello
  
  input: cksli output: slick, licks
  
  Rather than use a brute force technique that computes all possible
  character combinations for each input target and compares them to a
  dictionary, you want to use a more efficient technique.


The approach I was considering was to pre-compute impossible string onsets in the target language. For example, in English, the onset sequences ^ck and ^ng are not permissable because they violate the orthographic and phonotactic constraints of the language. Given an off-line list of impossible_sequences at run time you would incrementally build possible "words" from the target. During each iteration the possible word is checked against the impossible_sequences list and if it matches the search
down that search branch is terminated. The following pseudo-code in R uses for loops to illustrate my idea.

target &lt;- "cksli"
impossible_list &lt;- c("ck", "ng", "rt", "zz") # pre-computed not-possible English onsets

for (i in 1:nchar(target)) {
  word &lt;- substr(target, i, i)
  if (word %in% impossible_list) break
  for (j in 2:nchar(target)) {
    word &lt;- paste0(word, substr(target, j, j))
    if (word %in% impossible_list) break
    for (k in 3:nchar(target)) {
      ### same logic
      ### goes deeper and deeper
    }
  }
}


(1) Are there any issues with the underlying logic of my proposal?
(2) Obviously nested for loops are inelegant - Could one do this recursively and if so, how?
(3) What other approaches should be considered?
A simple solution is store the words in a dictionary (since you have to store them in some data structure) whose key is the character distribution; e.g., Counter("hello") = {h: 1, e: 1, l: 2, o: 1}. Querying the dictionary would give you the anagrams.

For storing the immutable key (character distribution) can either use a tuple list, incurring a sort, or you can use a vector the length of your alphabet (26). So you can make a speed-space trade-off in the preparation stage; the look-ups are constant time, not counting the time it takes to calculate the character distribution of the query word. If you go the latter, fixed-width route, you can make another trade-off by hashing the key, since you know the cardinality of the input (number of unique words).