Gibt es einen effizienten Algorithmus um alle Wortkombination bestimmter Buchstaben zu erstellen?
Ich versuch die Frage mal ein bisschen präziser zu stellen: Man gibt einem Programm n Buchstaben, das Programm gibt jetzt alle möglichen Wortkombinationen aus diesen Buchstaben zurück, sodass für zb 6 Buchstaben 6! = 720 Wörter ausgegeben werden.
Ich habe mir bereits etwas dazu überlegt, aber der Algorithmus ist extrem ineffizient: Ich lasse alle Wörter der Länge von a bis z durch, also bei n=6 zb. aaaaaa, aaaaab, aaaaac, ... usw. und überprüfe dabei den Wert und die Anzahl eines Charakters, wenn Wert und Anzahl mit meinen eingegeben Buchstaben übereinstimmt wird das Wort zurückgegeben, ansonsten wird das nächste Wort betrachtet und dasselbe noch mal überprüft. Da nur n! Wörter gefunden werden können bricht das Programm dann ab wenn n! Wörter gefunden wurden (möglicherweise auch früher, wenn sich unter den eingegeben Buchstaben Dopplungen befinden). Das Problem ist, dass dieser Algorithmus extrem ineffizient ist, da er bis zu 26^n - n! falsche Wörter durchgehen kann bis er fertig wird, die 26 Potenz ist natürlich derbe, deshalb wollte ich fragen, ob es vielleicht einen clevereren Algorithmus gibt der das besser machen kann.
Vielleicht sowas in der Form, dass bestimmte Elemente an bestimmten Indizes auf eine bestimmte Art und Weise mit einem anderen Element vertauscht werden, sodass in jedem Schritt ein neues gesuchtes Wort entsteht und somit nur n! Rechenschritte benötigt werden, gibts sowas?
5 Antworten
Was du suchst nennt sich Permutationen. Hier ist ein relativ schneller Algorithmus in JavaScript.
function perm(a, n) {
if(n === a.length) {
console.log(a);
} else {
for(let i = n; i < a.length; i++) {
let t = a[i]; a[i] = a[n]; a[n] = t;
perm(a, n + 1);
t = a[i]; a[i] = a[n]; a[n] = t;
}
}
}
a ist dabei die Liste mit den Buchstaben und n muss 0 sein.
Es geht aber noch ein wenig schneller, indem man jedes mal nur einmal vertauscht anstatt wie in meinem Beispiel zweimal. Das ist hier erklärt: https://en.wikipedia.org/wiki/Heap%27s_algorithm
Rekursiv geht das prima:
main:
all_permutations([A,B,C,D,E], []);
function all_permutations(residual_set, current_word)
{
if (residual_set = [])
{
show current_word;
} else
{
for (letter : residual_set)
{
all_permutations(residual_set - letter, current_word + letter);
}
}
}
Wieso tut es das? Die Menge der verbleibenden Buchstaben wird immer kleiner, und ich habe eine Abbruchbedingung, wenn diese Menge leer ist. Übersehe ich da was?
Die Menge aller möglichen Kombinationen steigt exponentiell an -> stackoverflow
Das Ding hat Rekursionstiefe n, nicht n!, das ist überhaupt kein Problem.
n! steigt übrigens überexponentiell an.
Wieso willst du Wörter von a-z generieren, wenn du sowieso eine Liste der Wörter z.B. [b,f,k,i,o,i] eintippst? Nimm doch einfach diese Liste her & generiere die Wörter.
Wie kommst Du auf 720 Wörter? Das bedeutete, Du nutztest nur sechs verschiedene Buchstaben.
Es gibt dreißig Buchstaben im Deutschen, die bei einer sechsbuchstabigen Zeichenkette 729 Millionen Möglichkeiten ergeben.
Wenn die vermehrt unsinnigen Kombinationen auslässt, bleiben bestimmt noch mehrere Tausend.
Wie kommst Du denn auf n! ? Bei 6 Buchstaben komme ich auf 26^6 = 308.915.776
oder ich habe die Beschreibung falsch verstanden.
n Objekte kann man auf n! Weisen anordnen, also kann man zb aus den 6 Buchstaben a b c d e f insgesamt 720 unterschiedliche Wörter bilden
Rekursiv fliegt dir das ding um die ohren, minjung