So geht das!

Nachdem sich in letzter Zeit die Fragen, wie denn der Anagramm-Generator funktioniert, häuften, habe ich mich endlich mal daran gemacht, hier auch eine kurze Beschreibung der Funktionsweise zur Verfügung zu stellen. Folgende Schritte werden ausgeführt:
  1. Einlesen der Wortliste, aussortieren aller Wörter, die andere als die angegebenen Buchstaben (=Suchwort) enthalten
  2. Sortieren dieser (Rest-)Liste nach der Länge, so daß das längste Wort zuerst kommt.
  3. nächstes Wort aus der Liste wählen (am Anfang: erstes Wort)
  4. Restbuchstabenliste aufbauen, indem man die Buchstaben dieses Wortes aus den bisherigen Restbuchstaben entfernt (am Anfang: Restbuchstaben = alle Buchstaben des Suchbegriffs)
  5. die Liste ab dem gerade betrachteten Wort (exklusive) durchgehen, bis ein Wort gefunden wird, daß aus allen oder einem Teil der restlichen Suchbuchstaben gebildet werden kann.
    a) Wenn ein Wort gefunden wird, das aus sämtlichen Restbuchstaben besteht, dann wurde ein Anagramm gefunden. Dieses besteht aus den nacheinander gefundenen Wörtern. Es wird ausgegeben und dann geht die Suche bei Punkt 5 weiter.
    b) Besteht ein gefundenes Wort nicht aus allen Restbuchstaben, dann rekursiv weiter bei Punkt 4.
    c) Wenn keines mehr gefunden wird, dann Rücksprung (also Programmende oder höhere Rekursionsstufe)
Wenn man doppelte Wörter zulassen will, dann muß man die Liste bei der Suche nach dem Punkt 5b inklusive dem gerade betrachteten Wort weiter durchgehen.

Ich hoffe, ich konnte das klar darlegen. Wenn nicht -> fragen!

Das ganze ist die Kurzform, verschiedene Optimierungen wurden hier nicht beachtet. Für eine genauere Beschreibung verweise ich auf die Wordplay-Dokumentation (englisch), in der Evans A Criswell den rekursiven Algorithmus folgendermaßen beschreibt: 


int recursive_anagram (string, accumulation, level):
{
  if no vowels in string, decrement level, return   (dead end)
  go through list of important candidate words:  for each:
  {
    attempt to extract the word from the string passed into the function.
    if extraction not possible, continue (try next word)
    if extraction was perfect (left no letters), print the anagram
                       (accumulation plus the word), then decrement the level, 
                       return 
    if extraction was successful, but left some letters, add the word to
                       accumulation, increment level, and call the function
                       with args (<<whatever is left after extraction>>,
                                  accumulation, and level)
  }
  if no extractions were a success, decrement level and return.
  decrement level and return anyway, since we're at the end.  :-)
}
Zurück zur Hauptseite