Algoritmo per ottenere un elenco di tutte le parole che sono anagrammi di tutte le sottostringhe (scrabble)?

Question

Ad esempio, se la stringa di input è helloworld voglio che l'output sia come:

do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...

tutta la strada fino alla parola più lunga che è un anagramma di una sottostringa di helloworld.Come Scrabble, per esempio.La stringa di input può essere di qualsiasi lunghezza, ma raramente più di 16 caratteri.

Ho fatto una ricerca e venire con strutture come un trie, ma io sono ancora sicuri di come fare questo.

Answer 1

La struttura utilizzata per tenere il vostro dizionario di voci valide avrà un enorme impatto sull'efficienza. Organizza come un albero, radice essendo lo zero lettera "parola" singolare, la stringa vuota. Ogni bambino di radice è una singola prima lettera di una parola possibile, figli di coloro essendo la seconda lettera di una parola possibile, ecc, con ogni nodo contrassegnato come se si forma effettivamente una parola o meno.

La vostra funzione tester sarà ricorsiva. Si inizia con zero lettere, trova dall'albero di voci valide che "" non è una parola ma ha figli, in modo da chiamare il tester in modo ricorsivo con la tua parola di partenza (di nessuna lettera) con l'aggiunta di ogni lettera rimanendo disponibili presso il stringa di input (che tutti in quel punto). Controllare ogni voce di una lettera in albero, se valido rendere nota; se i bambini, ri-chiamata di funzione tester aggiungendo ciascuno dei restanti lettere disponibili, e così via.

Così, per esempio, se la stringa di input è "HelloWorld", si sta andando a chiamare prima la funzione ricorsiva tester con "", passando per le restanti lettere disponibili "HelloWorld" come secondo parametro. Funzione vede che "" non è una parola, ma figlio "h" non esiste. Così si definisce con "h", e "elloworld". Funzione vede che "h" non è una parola, ma figlio "e" esiste. Così si definisce con "lui" e "lloworld". Funzione che vede "e" è segnato, in modo da "lui" è una parola, prendere nota. Inoltre, bambino "l" esiste, così la prossima chiamata è "hel" con "loworld". Sarà la prossima trovare "inferno", poi "ciao", allora dovrà tornare indietro e probabilmente il prossimo trovare "vuoto", prima di eseguire tutta la via d'uscita per la stringa vuota di nuovo e poi a partire da "e" parole successive.

Answer 2

Non ho potuto resistere al mio propria implementazione. Si crea un dizionario di classificare tutte le lettere in ordine alfabetico, e li mappatura alle parole che possono essere creati da loro. Si tratta di una (n) O start-up che elimina la necessità di trovare tutte le permutazioni. Si potrebbe implementare il dizionario come un trie in un'altra lingua per ottenere incrementi nella velocità più veloci.

Il comando "getAnagrams" è anche un'operazione O (n) che cerca ogni parola nel dizionario per vedere se si tratta di un sottoinsieme della ricerca. Facendo getAnagrams ( "radiotelegraphically")"(una parola lettera 20) ha preso circa 1 secondo sul mio portatile, ed è tornato 1496 anagrammi.

# Using the 38617 word dictionary at 
# http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt
# Usage: getAnagrams("helloworld")

def containsLetters(subword, word):
    wordlen = len(word)
    subwordlen = len(subword)

    if subwordlen > wordlen:
        return False

    word = list(word)
    for c in subword:
        try:
            index = word.index(c)
        except ValueError:
            return False
        word.pop(index)
    return True

def getAnagrams(word):
    output = []
    for key in mydict.iterkeys():
        if containsLetters(key, word):
            output.extend(mydict[key])

    output.sort(key=len)
    return output

f = open("dict.txt")
wordlist = f.readlines()
f.close()

mydict = {}
for word in wordlist:
    word = word.rstrip()
    temp = list(word)
    temp.sort()
    letters = ''.join(temp)

    if letters in mydict:
        mydict[letters].append(word)
    else:
        mydict[letters] = [word]

Un esempio di esecuzione:

>>> getAnagrams("helloworld")
>>> ['do', 'he', 'we', 're', 'oh', 'or', 'row', 'hew', 'her', 'hoe', 'woo', 'red', 'dew', 'led', 'doe', 'ode', 'low', 'owl', 'rod', 'old', 'how', 'who', 'rho', 'ore', 'roe', 'owe', 'woe', 'hero', 'wood', 'door', 'odor', 'hold', 'well', 'owed', 'dell', 'dole', 'lewd', 'weld', 'doer', 'redo', 'rode', 'howl', 'hole', 'hell', 'drew', 'word', 'roll', 'wore', 'wool','herd', 'held', 'lore', 'role', 'lord', 'doll', 'hood', 'whore', 'rowed', 'wooed', 'whorl', 'world', 'older', 'dowel', 'horde', 'droll', 'drool', 'dwell', 'holed', 'lower', 'hello', 'wooer', 'rodeo', 'whole', 'hollow', 'howler', 'rolled', 'howled', 'holder', 'hollowed']

Answer 3

La struttura dei dati che si desidera è chiamato un Diretto aciclici Graph Word (Dawg) , ed è è descritto da Andrew Appel e Guy Jacobsen nel loro articolo "Fastest Programma Scrabble del mondo" che, purtroppo, hanno scelto di non rendere disponibile online gratuito. Un abbonamento ACM o una biblioteca universitaria lo otterrà per voi.

Ho implementato questa struttura dati in almeno due lingue --- è semplice, facile da implementare, e molto, molto veloce.

Answer 4

Un approccio ingenuo è quello di generare tutte le "sottostringhe" e, per ciascuno di essi, verificare se è un elemento della serie di parole accettabili. Per esempio, in Python 2.6:

import itertools
import urllib

def words():
  f = urllib.urlopen(
    'http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt')
  allwords = set(w[:-1] for w in f)
  f.close()
  return allwords

def substrings(s):
  for i in range(2, len(s)+1):
    for p in itertools.permutations(s, i):
      yield ''.join(p)

def main():
  w = words()
  print '%d words' % len(w)
  ss = set(substrings('weep'))
  print '%d substrings' % len(ss)
  good = ss & w
  print '%d good ones' % len(good)
  sgood = sorted(good, key=lambda w:(len(w), w))
  for aword in sgood:
    print aword

main()

emetterà:

38617 words
31 substrings
5 good ones
we
ewe
pew
wee
weep

Naturalmente, come altre risposte hanno sottolineato, organizzare i dati di proposito può notevolmente accelerare il vostro tempo di esecuzione - anche se la migliore organizzazione dei dati per un cercatore anagramma veloce potrebbe essere diverso ... ma questo dipenderà in gran parte dalla natura del dizionario di parole consentite (poche decine di migliaia, come qui -? o milioni). Hash-mappe e "firme" (sulla base di smistamento delle lettere di ogni parola) devono essere considerate, così come tentativi & c.

Answer 5

Quello che vuoi è un'implementazione di un set di potenza.

Anche guardare Eric Lipparts blog, ha scritto un blog su questa cosa un po ' indietro

EDIT:

Qui è un'implementazione che ho scritto di ottenere il powerset da una data stringa...

private IEnumerable<string> GetPowerSet(string letters)
{
  char[] letterArray = letters.ToCharArray();
  for (int i = 0; i < Math.Pow(2.0, letterArray.Length); i++)
  {
    StringBuilder sb = new StringBuilder();
    for (int j = 0; j < letterArray.Length; j++)
    {
      int pos = Convert.ToInt32(Math.Pow(2.0, j));
      if ((pos & i) == pos)
      {
        sb.Append(letterArray[j]);
      }
    }
    yield return new string(sb.ToString().ToCharArray().OrderBy(c => c).ToArray());
  }
}

Questa funzione dà la powerset di caratteri che compongono il passato nella stringa, ho quindi possibile utilizzare questi tasti in un dizionario degli anagrammi...

Dictionary<string,IEnumerable<string>>

Ho creato il mio dizionario di anagrammi in questo modo...(probabilmente ci sono modi più efficienti, ma questo è stato semplice e un sacco abbastanza veloce con il torneo di scrabble elenco di parole)

wordlist = (from s in fileText.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries)
                let k = new string(s.ToCharArray().OrderBy(c => c).ToArray())
                group s by k).ToDictionary(o => o.Key, sl => sl.Select(a => a));

Answer 6

come Tim J , i post sul blog Eric Lippert s ' dove la prima cosa a venire in mente. Volevo aggiungere che ha scritto un follow-up sui modi per migliorare le prestazioni del suo primo tentativo.

• Un talismano nasality per l'analista sultana
• Santalic tailfans, seconda parte

Answer 7

Credo che il codice Ruby nelle risposte questa domanda sarà anche risolvere il problema.

Answer 8

Ho giocato un sacco di Wordfeud sul mio cellulare da poco ed ero curioso di sapere se potevo venire con qualche codice per darmi un elenco di parole possibili. Il codice seguente prende le vostre lettere availble sorgente (* per un jolly) e un array con un elenco principale di parole ammissibili (TWL, SOWPODS, ecc) e genera un elenco di corrispondenze. Lo fa cercando di costruire ogni parola nella lista principale dalle vostre lettere di origine.

Ho trovato questo argomento dopo aver scritto il mio codice, e non è sicuramente il più efficiente metodo di John Pirie o l'algoritmo DAWG, ma è ancora piuttosto veloce.

public IList<string> Matches(string sourceLetters, string [] wordList)
{
    sourceLetters = sourceLetters.ToUpper();

    IList<string> matches = new List<string>();

    foreach (string word in wordList)
    {
        if (WordCanBeBuiltFromSourceLetters(word, sourceLetters))
            matches.Add(word);
    }

    return matches;
}


public bool WordCanBeBuiltFromSourceLetters(string targetWord, string sourceLetters)
{
    string builtWord = "";

    foreach (char letter in targetWord)
    {
        int pos = sourceLetters.IndexOf(letter);
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
            continue;
        }


        // check for wildcard
        pos = sourceLetters.IndexOf("*");
        if (pos >= 0)
        {
            builtWord += letter;
            sourceLetters = sourceLetters.Remove(pos, 1);
        }


    }

    return string.Equals(builtWord, targetWord);

}