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

Spiderpig42

15.10.2019, 17:53

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

ShimaG

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Mathematik

15.10.2019, 17:11

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

Gurkenbruder

15.10.2019, 18:15

Rekursiv fliegt dir das ding um die ohren, minjung

ShimaG

15.10.2019, 18:25

@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?

Gurkenbruder

15.10.2019, 18:33

@ShimaG

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

ShimaG

15.10.2019, 19:28

@Gurkenbruder

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

n! steigt übrigens überexponentiell an.

Quotenbanane

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Mathematik

15.10.2019, 17:07

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

MatthiasHerz

15.10.2019, 17:15

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.

Lilalaunebaer69

15.10.2019, 17:10

Wie kommst Du denn auf n! ? Bei 6 Buchstaben komme ich auf 26^6 = 308.915.776
oder ich habe die Beschreibung falsch verstanden.

NettUndTolerant

Fragesteller

15.10.2019, 17:21

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

Lilalaunebaer69

16.10.2019, 10:43

@NettUndTolerant

Ach so - die Buchstaben sind vorgegeben.

Wie der Titel bereits aussagt soll ein Algorithmus entwickelt werden der am Ende die Anzahl der elemente der längsten kette von sich wiederholenden Zahlen ausgibt also beispiel: 1 1 1 1 2 2 2 2 2 1 2 4 4 4 4 4 4 4 4 4 soll 9 ausgeben da die reihe der vieren nach der 2 die längste kette ist mein Programm bis jetzt sieht wie folgt aus

meine Frage ist jetzt wo liegt hier mein Fehler?

...zur Frage

Kombinatorik: Wie viele Möglichkeiten gibt es?

Also vorab:

Ist mir durchaus bekannt!

Das hilft mir zu berechnen, wie viele Möglichkeiten es für eine Anzahl an Elementen n gibt und welche Elemente von dieser Anzahl doppelt vorkommen (k1,k2,kn)

Sagen wir ich habe zwei Buchstaben, von A bis Z, 26 mögliche Buchstaben pro Stelle.

Nun will ich wissen wie viele Möglichkeiten es gibt, diese 26 Buchstaben auf zwei Stellen anzuordnen.

.....

Da komme ich mit meiner schicken Permutationsformel nicht weit.

Hat jemand nen Tipp?

...zur Frage

Wenn unbestimmtes Wort dann Farbe in Excel?

Hallo an Alle!
Ich würde sehr gerne eine Zelle so formatieren, dass sobald ein Wort, oder auch nur Buchstaben eingegeben werden, eine Farbe erscheint.
Bei den bedingten Formationen bin ich bis jetzt nur auf die Möglichkeit gekommen nach bestimmten Wörtern zu formatieren. Mein Ziel ist es nach Unbestimmten Wörtern, oder gar Buchstaben im Allgemeinen zu formatieren.
Vielen herzlichen Dank bereits Vorab für Eure Hilfe!

...zur Frage

Ich suche ein Programm, mit dem ich aus bestimmten Buchstaben Wörter bilden kann?

Hallo, ich habe drei Wörter, und die Buchstaben daraus habe ich in Kästchen eingetragen und diese dann ausgeschnitten.

Jetzt suche ich eine Möglichkeit, ALLE Wörter, die man daraus bilden kann, am besten in einer Liste anzeigen zu lassen.

Beispiel: Ich habe das Wort "Datum". Wenn ich jetzt die Buchstaben anders anordne, kann z. B. "Mudat" oder "Duamt" daraus werden, oder oder oder. So. Und ich möchte das Wort eingeben und dann Enter drücken, und das Programm liefert mit alle Möglichkeiten, die ich habe, die Buchstaben des Worts neu anzuordnen und daraus andere Wörter zu bilden, auch wenn sie gar nicht existieren, wie z. B. "Mudat". Das ist egal.

Habt ihr eine Idee?

...zur Frage

Ich muss bei vielen Wörtern die Buchstaben zählen. Wie kann ich diesen Tick loswerden?

Ich muss bei vielen Wörtern die Buchstaben zählen. Dabei muss unbedingt eine gerade Anzahl herauskommen. Wenn ein Wort wie "Ampel" nur 5 Buchstaben hat, dann sehe ich das "p" als "pe" wegen der Aussprache damit es 4 Buchstaben sind. Außerdem stelle ich mir vor wie ich das Wort auf einer Tastatur eingebe und Spanne dementsprechend den linken Oberschenkel an für ein A, den rechten für ein L. Nervt extrem, kann mich schlecht konzentrieren. Was kann ich dagegen machen? Gruß

...zur Frage

Python Wort aus Zufallsliste?

Hallo liebe Community,

wie könnte ein Programm in Python aussehen, welches:

-Aus den 26 Buchstaben des Deutschen Alphabetes zufällige Buchstaben heraussucht

-Diese aneinanderreiht

-Schaut wann ein bestimmtes Wort in dieser Buchstabenkette auftaucht

-Und die Schritte dabei zählt

Den ersten Punkt habe ich schon, jedoch weiß ich nicht genau, wie ich weitermachen soll...

Vielen Dank!!!

PS: Bin ein Python Anfänger

...zur Frage

Probleme mit C-Programmierung: Zahlen sortieren?

Hallo, ich habe folgendes Programm geschrieben und komme einfach nicht weiter. Das Programm zählt die Buchstaben einer .txt Datei und gibt ebenso deren Häufigkeit an. Ich soll jetzt noch die Anzahl der Buchstaben beginnen mit der größten Zahl sortieren. Die Buchstaben müssen dabei auch stimmen und natürlich die Häufigkeit. Kann mir jemand dabei helfen?

So weit bin ich gekommen, eine Beispiel txt Datei wurde implementiert. Ich programmiere mit Codeblocks.

#include <stdio.h>

include

char dateiname[40]; int anweisung1;

int main(int argc, char **argv) { if (argc != 2) { printf("Der Dateiname fehlt\n"); return 0; }

FILE *fp = fopen(argv[1], "r");
if (fp == NULL)
{
    printf("Die Datei kann nicht geoeffnet werden\n");
    return 0;
}

double anzahl[26] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int gesamt = 0;


while (1) //Zähschleife
{
    int buchstaben = fgetc(fp);
    if (buchstaben < 0)
    {
        break;
    }
    if (buchstaben >= 'A' && buchstaben <= 'Z') //Zählschleife für Großbuchstaben
    {
        anzahl[buchstaben - 'A']++;
        gesamt++;
    }
    else if (buchstaben >= 'a' && buchstaben <= 'z')
    {
        anzahl[buchstaben - 'a']++; //Zähschleife für Kleinbuchstaben
        gesamt++;
    }
}


fclose(fp);

int anweisung;
printf("Dieses Programm zaehlt die die Buchstaben in einer .txt Datei\nund gibt die Haeufigkeit der Buchstaben an\n");
printf("Sie haben jetzt die Auswahl zwischen:\n");
printf("1. Die .txt Datei mit printf in der Konsole auszugeben\n");
printf("2. Eine neue .txt Datei zu speichern\n\n");
scanf("%d", &anweisung);

switch(anweisung)
{
case 1:
    printf("Die Gesamtzahl der Buchstaben lautet: %d\n",gesamt);

    int i;
    for (i = 0; i < 26; i++)
    {
        printf("%c : %0.lf", (i + 'A'), anzahl[i]);
        double prozente = anzahl[i]*100/gesamt;
        printf("\tHaeufigkeit: %.2lf%%\n",prozente);
    }
    return 0;

case 2:

    printf("\nBitte geben Sie den Dateinamen mit .txt an:\n\n");
    scanf("%s", dateiname);
    printf("\nIhre Datei heisst: %s.\n", dateiname);

    FILE* fp;
    fp = fopen(dateiname,"w");
    fprintf(fp,"Die Gesamtzahl der Buchstaben lautet: %d\n",gesamt);

    for (i = 0; i < 26; i++)
    {
        fprintf(fp,"%c : %0.1f\t  ", (i + 'A'), anzahl[i]);
        double prozente = anzahl[i]*100/gesamt;
        fprintf(fp,"Haeufigkeit: %.2lf%%\n",prozente);
    }
    return 0;
    fclose(fp);
}

}

...zur Frage

Wie filtert man bestimmte Wörter aus einem langem Text?

Hey,

ich würde gerne einen Automatismus haben,der bestimmte Wörter aus einem Text filtert und die Anzahl,wie oft dieses Wort vorkommt auch angibt. Kennt ihr vielleicht eine Webseite,Programm oder sonstiges dafür? Vielleicht habt ihr ja sogar einen Quellcode dafür.

Danke im Vorraus für eure Antworten! :)

...zur Frage

Excel - Liste mit Wörtern - Jedes Wort darf nur einmal vorkommen?

Hallo,

ich habe in Excel eine Liste mit Wörtern. In der Liste sind einige Wörter doppelt bzw. mehrfach enthalten. Kann ich mit irgendeiner Funktion die Wörter so bearbeiten, dass jedes Wort bzw. jede Wortkombination nur einmal vorkommt?

Vielen Dank im Voraus!

...zur Frage

Wie viele Buchstaben im Durchschnitt?

Wie viele Buchstaben haben die Wörter im Deutschen im Durchschnitt und welche Anzahl an Buchstaben kommt am häufigsten vor?

...zur Frage

gibt es eine Seite, die aus verschiedenen Buchstaben anzeigt welche Wörter man daraus machen kann?

also wenn ich z.B. die Buchstaben a, n, g, s und t eingebe, dann spuckt mir das Programm Angst und wenn es noch ein Wort gibt, was mit den Buchstaben gebildet werden kann, dieses Wort auch aus

...zur Frage

Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

...zur Frage

Diverse zahlenbasierte Eigenschaften von Wörtern?

Hallo zusammen,

im Rahmen eines Projektes benötige ich einige Eigenschaften von Wörtern, die irgendwie mit Zahlen in Verbindung gebracht werden können (um genau zu sein im Bereich von 15 bis 20).

Selber dachte ich schon an die Summe der einzelnen Buchstabenwerte (also "a"=1, "b=2", "c=3", usw.), die einfache Anzahl der Buchstaben in einem Wort, der Anfang des Wortes (wie ACHTung o.Ä.), die Anzahl Silben oder auch die Anzahl an Buchstaben mit einer "geschlossenen Form" (also z.B. P, B, D, R, usw.)

Ich brauche aber noch mehr davon, kennt ihr vielleicht noch mehr solcher Eigenschaften?

...zur Frage

VBScript: Zeichen zählen?

Wenn ich Wörter zählen möchte mache ich das in Kopf was ein bisschen doof wird wenn man so um die 300 - 400 Wörter zählen muss. Dann kam mir die Idee: Wenn ich ein Wort gezählt habe haue ich einmal auf die Leertaste/eine Taste. Am Schluss drücke ich Enter und mein Programm soll zählen wie viele Zeichen ich eingegeben hab. Wie würde das gehen?

Worte = InputBox("Gib einfach Buchstaben und leerstellen ein und diese Werden dann gezählt!","Wörter zählen")

'Hier Wörter zählen

'_____________________________________________


'_____________________________________________

msgbox ""&Anzahl&" Wörter",0+64,"Wörter gezählt"
'Ende

î hier eine kleine Vorgabe ;)

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen