Algorithmus zur Generierung aller möglichen Buchstaben-Kombinationen der gegebenen Zeichenfolge bis auf 2 Buchstaben

Für den Zweck des Schreibens ein anagram solver die Art, die Sie im Zusammenhang mit dem Algorithmus, den Sie fordert, ist nicht notwendig. Es ist auch SEHR teuer.

Schauen wir uns eine 6-Buchstaben-Wort wie MONKEY zum Beispiel. Alle 6 Buchstaben des Wortes sind unterschiedlich, so dass Sie schaffen würden:

• 6*5*4*3*2*1 verschiedene 6-Buchstaben-Wörter
• 6*5*4*3*2 verschiedene 5-Buchstaben-Wörter
• 6*5*4*3 andere 4-Buchstaben-Wörter
• 6*5*4 verschiedenen 3-Buchstaben-Wörter
• 6*5 verschiedene 2-Buchstaben-Wörter
• Für insgesamt 1950 Worten

Nun, vermutlich versucht man nicht ausspucken alle 1950 Wörtern (z.B. 'OEYKMN') als anagramme (was Sie auch sind, aber die meisten von Ihnen sind auch Kauderwelsch). Ich vermute, Sie haben ein Lexikon, Juristisches Englisch Wörter und Sie wollen einfach nur, um zu überprüfen, ob diese Wörter sind anagramme der Suchbegriff, mit der option, nicht alle Buchstaben.

Wenn das der Fall ist, dann ist das problem einfach.

Bestimmen, wenn 2 Wörter sind anagramme voneinander alles, was Sie tun müssen, ist zu zählen, wie oft die einzelnen Buchstaben werden verwendet, und vergleichen Sie diese zahlen!

Wir beschränken uns auf nur 26 Buchstaben A-Z, groß-und Kleinschreibung. Was Sie tun müssen, ist schreiben eine Funktion countLetters nimmt ein Wort und gibt ein array mit 26 Nummern. Die erste Zahl im array entspricht der Anzahl der Buchstaben A im Wort, die zweite Zahl entspricht der Anzahl der B usw.

Dann, zwei Worte W1 und W2 sind genaue Anagramm, wenn countLetters(W1)[i] == countLetters(W2)[i] für jeden i! Das heißt, jedes Wort verwendet jedem Buchstaben die gleiche Anzahl von Zeiten!

Für das, was ich nennen würde die sub-anagramme (MONEY ist ein sub-Anagramm von MONKEY), W1 ist ein sub-Anagramm von W2 wenn countLetters(W1)[i] <= countLetters(W2)[i] für jeden i! Das heißt, die sub-Anagramm kann weniger von bestimmten Buchstaben, aber nicht mehr!

(Hinweis: MONKEY ist auch ein sub-Anagramm von MONKEY).

Dies sollte Ihnen eine schnell genug-Algorithmus, wo in einem gegebenen query-string, alles, was Sie tun müssen, ist Lesen Sie durch das Wörterbuch einmal und vergleicht die Buchstaben zählen-array jedes Wort gegen das Brief-count-array mit den query-Wort. Sie können tun, einige kleinere Optimierungen, aber das sollte gut genug sein.

Alternativ, wenn Sie wollen höchste performance, Sie können Vorverarbeiten das Wörterbuch (die im Voraus bekannt ist), und erstellen Sie einen gerichteten azyklischen Graphen von sub-Anagramm Beziehung.

Hier ist ein Teil eines solchen Graphen für die Abbildung:

 D=1,G=1,O=1  ----------> D=1,O=1
  {dog,god}   \            {do,od}
               \
                \-------> G=1,O=1
                           {go}

Grundsätzlich jeder Knoten ist ein Eimer für alle Wörter, die den gleichen Brief count-array (d.h. Sie sind genau anagramme). Dann gibt es einen Knoten aus N1 zu N2 wenn N2's array ist <= (wie oben definiert) N1's array (die Sie durchführen können, transitive Reduktion zu speichern, die geringste Menge der Kanten).

Dann eine Liste aller sub-anagramme eines Wortes, alles, was Sie tun müssen ist, finden Sie die entsprechenden Knoten, um Buchstaben zu zählen, array rekursiv erkunden, alle Knoten erreichbar sind Knoten. Alle Ihre Eimer enthalten würde, die sub-anagramme.

Du willst eine Art von arrangements. Wenn Sie vertraut sind mit der permutation Algorithmus dann wissen Sie, Sie haben einen check, um zu sehen, wenn Sie generiert haben genug zahlen. Nur ändern limit:

Ich weiß nicht, AS3, aber hier ist ein pseudocode:

st = an array
Arrangements(LettersInYourWord, MinimumLettersInArrangement, k = 1)
  if ( k > MinimumLettersInArrangements )
  {
    print st;
  }

  if ( k > LettersInYourWord )
    return;      

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

für "abc" und-Anordnungen(3, 2, 1); dies drucken:

ab
abc
ac
acb
...

Wenn Sie möchten, dass diese mit drei ersten, und dann solche mit zwei, betrachten Sie dieses:

st = an array
Arrangements(LettersInYourWord, DesiredLettersInArrangement, k = 1)
  if ( k > DesiredLettersInArrangements )
  {
    print st;
    return
  }

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

Dann für "abc" nennen Arrangements(3, 3, 1); und dann Arrangements(3, 2, 1);

Es ist einfach O(N), wobei n die Größe des Vokabulars.
Sortieren Sie die Buchstaben in jedem Wort in den Wortschatz oder besser, erstellen Sie binäre Maske und Sie dann zu vergleichen mit Buchstaben, die Sie haben.