Word Jumble Algorithm

Question

Dada una mezcla de palabras (por ejemplo, ofbaor), ¿cuál sería un enfoque para descifrar las letras para crear una palabra real (es decir, foobar)? Pude ver que esto tiene un par de enfoques, y creo que sé cómo lo haría en .NET, pero tengo curiosidad por ver cómo se ven otras soluciones (siempre feliz de ver si mi solución es óptima o no).

Esto no es tarea o algo por el estilo, acabo de ver un revoltijo de palabras en la sección de comics locales del periódico (sí, un buen periódico de moda), y el ingeniero en mí comenzó a pensar.

editar: publique un código falso o un código real si puede; Siempre es bueno intentar expandir el conocimiento del lenguaje viendo ejemplos como este.

Answer 1

Tenga un diccionario que esté codificado por las letras de cada palabra ordenadas. Luego, tome una y otra vez las letras: busque todas las palabras en el diccionario por esa cadena de letras ordenadas.

Así, como ejemplo, las palabras 'oso' y 'desnuda' sería en el diccionario de la siguiente manera:

key word 
----- ------ 
aber bear 
aber bare 

Y si se te da el revoltijo, 'earb', que había clasifique las letras para 'aber' y sea capaz de buscar ambas palabras posibles en el diccionario.

Answer 2

Crea todas las permutaciones de la cadena y búscalas en un diccionario.

Puede optimizar buscando cadenas más cortas que comiencen palabras, y si no hay palabras de longitud adecuada en el diccionario que comiencen con esas cadenas, eliminando las permutaciones comenzando con esas letras de mayor consideración.

Answer 3

CodeProject tiene un par de artículos here y here. El segundo usa recursividad. Wikipedia también describe un par de algoritmos here. El artículo de Wikipedia también menciona un programa llamado Jumbo que utiliza un enfoque más heurístico que resuelve el problema como lo haría un ser humano. Parece que hay algunos enfoques para el problema.

Answer 4

Dependiendo de la longitud de la cadena enfoque de torbellino podría ser más rápido, sino una forma alternativa de hacer que los que tienen más o menos O (n) la complejidad es en lugar de crear todas las permutaciones de la cadena y mirando hacia arriba, se repase todas las palabras en el diccionario y vea si cada una puede construirse a partir de la cadena de entrada.

Un realmente algoritmo inteligente que sabe el número de palabras en el diccionario de antemano podría hacer algo como esto:

sort letters in jumbled string 
if factorial(length of jumbled string) > count of words in dictionary: 
    for each word in dictionary: 
     sort letters in dictionary word 
     if sorted letters in dictionary word == sorted letters in jumbled string: 
      append original dictionary word to acceptable word list 
else: 
    create permutation list of jumbled letters 
    for each permutation of letters: 
     search in dictionary for permutation 
     if permutation in dictionary: 
      add word to acceptable word list 

Answer 5

http://www.codeproject.com/KB/game/Anagrams2.aspx