Word Jumble Algorithm

Question

Data una parola jumble (vale a dire ofbaor), quale sarebbe un approccio per decodificare le lettere per creare una parola reale (ad esempio, il foobar)? Ho potuto vedere questo con un paio di approcci, e penso di sapere come lo farei in .NET, ma sono curioso di vedere come appaiono alcune altre soluzioni (sempre felice di vedere se la mia soluzione è ottimale o meno).

Questo non è compito o qualcosa del genere, ho appena visto una parola mescolarsi nella sezione del fumetto locale (sì, una buona vecchia carta stampata), e l'ingegnere in me ha iniziato a pensare.

modifica: si prega di inviare qualche pseudo codice o codice reale se è possibile; è sempre bello provare ad espandere la conoscenza della lingua vedendo esempi come questo.

Answer 1

Avere un dizionario che è digitato dalle lettere di ogni parola in ordine. Quindi prendi un po 'di guazza e ordina le lettere - cerca tutte le parole del dizionario con quella stringa di lettere ordinate.

Così, ad esempio, le parole 'orso' e 'vuota' sarebbe nel dizionario come segue:

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

E se sei dato il groviglio, 'earb', si sarebbe ordina le lettere su "aber" e cerca le parole possibili nel dizionario.

Answer 2

Creare tutte le permutazioni della stringa e cercarle in un dizionario.

È possibile ottimizzare la ricerca di stringhe più corte che iniziano le parole e se non ci sono parole di lunghezza adeguata nel dizionario che iniziano con quelle stringhe, eliminando le permutazioni che iniziano con quelle lettere da un'ulteriore considerazione.

Answer 3

CodeProject ha un paio di articoli here e here. Il secondo usa la ricorsione. Wikipedia delinea anche un paio di algoritmi here. L'articolo di Wikipedia menziona anche un programma chiamato Jumbo che usa un approccio più euristico che risolve il problema come farebbe un umano. Sembra che ci siano alcuni approcci al problema.

Answer 4

A seconda della lunghezza della stringa, l'approccio di WhirlWind potrebbe essere più veloce, ma un modo alternativo di farlo che ha più o meno O (n) complessità è invece di creare tutte le permutazioni della stringa e cercarle, tu passare attraverso tutte le parole del dizionario e vedere se ciascuna può essere costruita dalla stringa di input.

Un davvero algoritmo intelligente che conosce il numero di parole nel dizionario in anticipo potrebbe fare qualcosa di simile:

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