AnagramSolver

# simplified version
class Node():
  def __init__(self, value, children, last=False):
    self.value = value
    self.children = children
    self.isword = last

class WordList(object):
  def __init__(self, words):
    self.root = Node(None,dict())

    ''' naive building of the tree '''
    for word in wlist:
      self.insert(word.lower())

  def insert(self, word):
    root = self.root
    size = len(word)-1
    for i,char in enumerate(word):
      item = root.children.get(char)
      if item is None:
        n = Node(char,dict(),i==size)
        root.children[char] = n
        root = root.children[char]
      else:
        if i==size:
          item.isword = True
        root = item

  def match_chars(self,chars,root=None, pre=''):
    '''
      recursivly walk through nodes and gather all the
      words that fits the given characters
    '''
    res = set()
    if root is None: root = self.root

    for i,char in enumerate(chars):
      new_chars = chars[:]
      del new_chars[i]

      item = root.children.get(char)
      if item is None:
        continue

      node = item
      if node.isword:
        res.add(pre+char)
      res.update(self.match_chars(new_chars,node,pre+char))
    return res


class AnagramSolver(object):
  def __init__(self,words):
    self.dictionary = WordList(words)

  def __buildAnagrams(self, word, alts, agram=[]):
    res = []
    for alt in alts:
      tmp = list(word)
      imp = False
      for c in alt:
        try:
          idx = tmp.index(c)
          del tmp[idx]
        except:
          imp = True
          break;
      if imp: continue;
      n = agram[:] + [alt]
      if len(tmp) == 0: #only insert if all chars are used
        res.append(n)
      else:
        res += self.__buildAnagrams(tmp, alts, n)

    return res

  def generateAnagrams(self, word, limit=0):
    if limit < 0:
      raise ValueError('Limit less than 0 not supported')

    chars = list(word.lower())
    words = self.dictionary.match_chars(chars)
    result = sorted(self.__buildAnagrams(chars,words))
    if limit != 0:
      result = [l for l in result if len(l) <= limit]
    return result



if __name__ == '__main__':
  from time import time
  with open('includes/wlist.txt') as f:
    wlist = f.read().splitlines()

  solver = AnagramSolver(wlist)
  print solver.generateAnagrams('officekey')