Vor geraumer Zeit befasste ich mich mit Anagrammen, also Wörtern oder Sätzen, die durch die Umstellung einzelner oder mehrerer Buchstaben entstehen. Ein Beispiel hierfür wäre der Name “T. T. Kreischwurst” aus dem Roman Die Stadt der träumenden Bucher von Walter Moers, welches ein Anagramm aus dem Namen “Kurt Schwitters” ist.
Die Stadt der Schriftsteller-Anagramme #
Moers benutzt in seinem Roman, dass als “Liebeserklärung an das Lesen und die Literatur” bezeichnet werden kann, Anagramme von Namen bekannter Schriftsteller und Künstler um mit ihnen seine Romanfiguren, welche ebenfalls Schriftsteller sind, zu schmücken. Es macht recht viel Spaß, die Namen der Romanfiguren zu entziffern, was bei einem “Ohjann Golgo von Fontheweg” (Johann Wolfgang von Goethe) nicht schwer ist, bei vielen anderen aber durchaus. Einige Fans diskutieren die möglichen Lösungen auch auf ihren Blogs.
Mich interessierte, wie man solche Anagramme durch den Computer erkennen und aufschlüsseln lassen könnte.
Anagramme als Permutationen #
Jedes Wort kann dabei N! Permutationen bilden (Variation ohne Wiederholung), mit N=Anzahl der Buchstaben. (Da es sich bei Moers um Namen handelt, ist die Rücksicht auf “sinnvolle” Worte nicht so relevant.) Ob zwei Wörter ineinander überführt werden können, hängt davon ab, ob sie die gleichen Buchstaben (in gleicher Anzahl) enthalten.
Normierte Permutation #
Um Wörter auf diese Eigenschaft hin zu prüfen, kann man alle Buchstaben jedes Wortes alphabetisch sortieren, also eine normierte Permutation bilden. Sollten die so entstandenen Permutationen gleich sein, handelt es sich um zwei Anagramme.
Ein Beispiel:
Die Worte hallo, ollah und alloh haben alle die normierte Permutation ahllo, welches der alphabetisch sortierten
Menge der enthaltenen Buchstaben entspricht. Ergo sind dies alle Anagramme des gleichen Wortes.
Programmatisch lässt sich die Norm wie folgt bilden:
public String createNorm(String word) {
final char[] letters = word.toCharArray();
Arrays.sort(letters);
return new String(letters);
}
Besitzt man also nun eine Liste aller Anagramm-Namen aus Moers Roman und eine aus allen bekannten Schriftstellern, so lässt sich die Suche auf einen einfachen Lookup (z. B. mittels des Hashcodes und einer Hashmap) reduzieren.