Gibt es einen effizienten Algorithmus um alle Wortkombination bestimmter Buchstaben zu erstellen?

3 Antworten

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);
}
}
}

Woher ich das weiß:Studium / Ausbildung – Studium und Promotion in Angewandter Mathematik

Rekursiv fliegt dir das ding um die ohren, minjung

0
@Gurkenbruder

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?

0
@ShimaG

Die Menge aller möglichen Kombinationen steigt exponentiell an -> stackoverflow

0
@Gurkenbruder

Das Ding hat Rekursionstiefe n, nicht n!, das ist überhaupt kein Problem.

n! steigt übrigens überexponentiell an.

0

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.

Woher ich das weiß:Studium / Ausbildung – Mathematik-Studium

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

Was möchtest Du wissen?