Chasse efficace pour les mots dans des lettres brouillées

1. construisez un Trie (Arbre préfixe) de votre dictionnaire. Vous voudrez peut-être le cacher.
2. Marchez sur cette trie et supprimez des branches entières qui ne correspondent pas à votre sac de lettres.

   À ce stade, votre trie est la représentation de tous les mots de votre dictionnaire pouvant être construit à partir de votre sac de lettres.

   1. prend juste le (s) plus long: -)

      EDIT: Vous pouvez également utiliser un DAGW (graphique de mot acyclique dirigé) qui aura moins sommets. Bien que je ne l'ai pas lu, cet article Wikipedia a un lien sur Le programme au Scrabble le plus rapide du monde .

Lorsque vous recherchez des mots de plus de 10 lettres, vous pouvez essayer de parcourir des mots (je pense qu'il n'y a pas tant de mots avec 10 lettres de plus de 10 lettres et de vérifier que vous avez besoin de lettres dans votre ensemble.

problème est que vous devez trouver tous ces len (mot)> = 10 mots en premier.

Alors, qu'est-ce que je ferais: Lorsque la lecture du dictionnaire a divisé les mots en 2 catégories: Shorts et Longs. Vous pouvez traiter des shorts en itérant sur chaque permutation possible. Que vous pouvez traiter des longs en itération de dessus et en le vérifiant, ils sont possibles.

Bien sûr, il existe de nombreuses optimisations possibles aux deux chemins.

implémentation de Jeroen Coupé idée de Sa réponse avec des lettres comptez: xxx pré>

sortie (pour mes petits 58000 mots dict): p> xxx pré> Notes: p>

• C'est une implémentation simple sans optimisations. P> Li>

• mots_list.txt code> - peut être / USR / Share / dict / mots code> sur Linux. P> LI> ul>

  update strong> p>

  au cas où nous devions trouver un mot une seule fois, et nous avons le dictionnaire avec des mots triés par longueur, par ex. Par ce script: P>

  from collections import Counter
  import sys
  
  
  def check_same_letters(origin_map, word):
      new_map = Counter(word)
      return all(new_map[let] <= origin_map[let] for let in word)
  
  def iter_longest_from_file(origin, file_path, min_length=1):
      origin_map = Counter(origin)
      origin_len = len(origin)
      with open(file_path) as f:
          for line in f:
              word = line.strip()
              if len(word) > origin_len:
                  continue
              if len(word) < min_length:
                  return
              if check_same_letters(origin_map, word):
                  yield word
  
  def find_longest_from_file(origin, file_path):
      return iter_longest_from_file(origin, file_path).next()
  
  if __name__ == '__main__':
      origin = sys.argv[1] if len(sys.argv) > 1 else 'abcdefghijklmnopqrstuvwxyz'
      print find_longest_from_file(origin, 'words_by_len.txt')
  

Ceci est similaire à un problème d'anagramme que j'ai travaillé auparavant. J'ai résolu que, en utilisant des nombres premiers pour représenter chaque lettre. Le produit des lettres pour chaque mot produit un numéro. Pour déterminer si un ensemble donné de caractères d'entrée suffit pour faire un travail, divisez simplement le produit du caractère d'entrée par le produit pour le numéro que vous souhaitez vérifier. S'il n'y a pas de reste, les caractères d'entrée sont suffisants. Je l'ai mis en œuvre ci-dessous. La sortie est la suivante:

import sys


def nextprime(x):
    while True:
        x += 1
        for pot_fac in range(2,x):
            if x % pot_fac == 0:
                break
        else:
            return x

def prime_generator():
    '''Returns a generator that produces the next largest prime as
    compared to the one returned from this function the last time
    it was called. The first time it is called it will return 2.'''
    lastprime = 1
    while True:
        lastprime = nextprime(lastprime)
        yield lastprime


# Assign prime numbers to each lower case letter
gen = prime_generator()
primes = dict( [ (chr(x),gen.next()) for x in range(ord('a'),ord('z')+1) ] )


product = lambda x: reduce( lambda m,n: m*n, x, 1 )
make_key = lambda x: product( [ primes[y] for y in x ] )


try:
    words = open('words').readlines()
    words = [ ''.join( [ c for c in x.lower() \
                if ord('a') <= ord(c) <= ord('z') ] ) \
            for x in words ]
    for x in words:
        try:
            make_key(x)
        except:
            print x
            raise

except IOError:
    words = [ 'reawaken','awaken','enwrap','weaken','weaker', ]

words = dict( ( (make_key(x),x,) for x in words ) )


inputs = sys.argv[1:] if sys.argv[1:] else [ 'raepkwaen', ]
for input in inputs:
    input_key = make_key(input)
    results = [ words[x] for x in words if input_key % x == 0 ]

    result = reversed(sorted(results, key=len)).next()
    print input,'--> ',result