Ich habe eine Datei mit sagen wir 1000 Wörtern und eine zweite Datei mit 100 Buchstaben. Ich möchte nun aus den 100 Buchstaben prüfen welche Wörter man aus der ersten Datei abbilden kann. Z.b. mit den mir 100 zur Verfügung stehenden Wörtern kann ich aus den 1000 Wörtern 7 bilden. Jetzt ist die Frage wie hoch der Aufwand ist bevor ich das programmiere, denn wenn es fast schon Richtung bruteforce geht dann kann man es vergessen und würde zu lange dauern. Daher die Frage ist das einfach und schnell lösbar und die zweite Frage wie würde man das machen vielleicht anhand vom Pseudocode. Ich würde C, Python oder C++ verwenden.
sozusagen ein Scrabblespiel Hundnase (Loriot) Darf man die Wörter und Buchstaben alphabetisch vorsortieren? Vielleicht sogar die Wörter selbst, also "Wörter" wird zu "eörrtw"
:
Bearbeitet durch User
Ja es darf alles vorvearbeitet werden wie man es möchte. Am ende soll nur aus den möglichen Buchstaben alle möglichen Wörter gefunden werden. Also bei deinem Beispiel muss nicht das Wort "eörrtw" gefunden werden, sondern "Wörter". "Wörter" ist einer dieser 1000 Wörter die in der Datei stehen.
Man braucht einen Wortschatz und mittels einer Abfrage des möglichs kurzen Wortes von vorhandenen Buchstaben. Hier eine Python Bibliothek eines Wortschatzes: https://github.com/lehmannro/libleipzig-python Für C/C++ habe ich auf die Schnelle nichts gefunden.
Nur damit ich es richtig verstehe: Du suchst aus der Wörter-Datei genau die Wörter, die ausschließlich Buchstaben aus der Buchstaben-Datei enthalten ? Willst also alle Wörter "streichen", die mindestens einen Buchstaben haben, der nicht in der Buchstaben Datei enthalten ist ?
jonas schrieb: > Ich habe eine Datei mit sagen wir 1000 Wörtern und eine zweite Datei mit > 100 Buchstaben. Ich möchte nun aus den 100 Buchstaben prüfen welche > Wörter man aus der ersten Datei abbilden kann. Z.b. mit den mir 100 zur > Verfügung stehenden Wörtern kann ich aus den 1000 Wörtern 7 bilden. Geht es dir darum, alle Kombinationen dieser Wörter zu finden oder nur die, mit der die meisten Wörter gebildet werden? Oder die, die möglichst viele Buchstaben aus dem zweiten Datei nutzt? Willi schrieb: > Nur damit ich es richtig verstehe: > Du suchst aus der Wörter-Datei genau die Wörter, > die ausschließlich Buchstaben aus der Buchstaben-Datei enthalten ? Soweit ich verstehe, darf jeder nur einmal vorkommen. > Willst also alle Wörter "streichen", die mindestens einen Buchstaben > haben, der nicht in der Buchstaben Datei enthalten ist ? Das wäre zwar nötig, würde aber nicht reichen.
Ganz spontan würde ich die Buchstaben in der zweiten Datei zählen. Also 3 mal A, 1 mal B, 0 mal C, 4 mal D… Dann würde ich für die Wörter zählen, wie oft welcher Buchstabe vorkommt. "Buchstabe" enthält zum Beispiel 1A,2B,1C,1E,1H,1S,1T,1U Für jeden enthaltenen Buchstaben würde ich die Buchstabentabelle aus der Datei der Reihe nach durchsuchen, ob die notwendige Anzahl an Buchstaben vorhanden ist. Buchstaben in der Datei zählen geht in O(Buchstaben), die Buchstaben pro Wort zählen geht in O(Wortlänge) und das muss O(Wörter) mal gemacht werden. Beim Vergleich bin ich nicht ganz sicher, sollte aber auch nicht zu lange dauern. Oder meinst du, man soll aus den gegebenen Buchstaben 'Sätze' bilden mit vorgegebenen Wörtern?
Dussel schrieb: > die Buchstaben pro > Wort zählen geht in O(Wortlänge) Stimmt gar nicht. Das müsste eher sowas wie O(Wortlänge*Buchstaben im Alphabet) sein.
wenn die Buchstaben sortiert sind, dann ist es überhaupt kein Problem. Aber natürlich muss man alle Buchstaben einzeln prüfen. Die Frage ist nur wie man das tut. Wenn man z.B. nur die Buchstaben a,A,b,B,c,C,...x,X,y,Y,z,Z nimmt, dann ist die Aufgabe einfach:
1 | const char* words[] = { "ONE", "two", "three", "four", |
2 | "FiVe", "six", "seven", "eight", |
3 | "nine", "no1", "2no", "n30" }; |
4 | |
5 | const size_t num_words = |
6 | sizeof (words) / sizeof (*words); |
7 | |
8 | for (size_t i = 0; i < num_words; i++) { |
9 | bool is_valid = true; |
10 | |
11 | for (size_t j = 0; j < strlen (words[i]); j++) { |
12 | if (toupper (words[i][j]) < 'A' || |
13 | toupper (words[i][j]) > 'Z') { |
14 | is_valid = false; |
15 | break; |
16 | }
|
17 | }
|
18 | |
19 | if (is_valid) { |
20 | printf ("yes:\t%s\n", words[i]); |
21 | }
|
22 | else { |
23 | printf ("no:\t%s\n", words[i]); |
24 | }
|
25 | }
|
Willi schrieb: > Nur damit ich es richtig verstehe: > Du suchst aus der Wörter-Datei genau die Wörter, > die ausschließlich Buchstaben aus der Buchstaben-Datei enthalten ? > Willst also alle Wörter "streichen", die mindestens einen Buchstaben > haben, > der nicht in der Buchstaben Datei enthalten ist Genau so ist es! Willi hat es so verstanden wie ich es meine Es sollen nur die Wörter übrig bleiben, die Buchstaben aus der Buchstaben Datei/Array enthalten. Wörter=[Auto, klein, Baum]; Buchstaben=[a t o k u z] würde bedeuten dass nur das Wort Auto übrig bleibt und ausgegeben wird. Ich habs jetzt mal ganz pragmatisch zwei for schleifen gedacht, eine für den Buchstabenden die andere für die Position im Wort.
xyz schrieb: > Die Frage ist nur wie man das tut. Wenn man z.B. nur die Buchstaben > a,A,b,B,c,C,...x,X,y,Y,z,Z nimmt, dann ist die Aufgabe einfach: Hier sollen aber alle 100 Buchstaben der zweiten Datei verwendet werden. Also wenn da 10 'A's vorkommen, dürfen die auch alle verwendet werden. So interpretiere ich jedenfalls die Aufgabe.
Wie intelligent soll denn der Algorithmus sein? Soll z.B. ein Wort wieder gestrichen werden, wenn sich herausstellt, dass man mit den verbrauchten Buchstaben auch zwei andere Wörter bilden könnte? Anders gesagt, muss man das Maximum an möglichen Wörtern finden? In Deutsch mit den nahezu beliebig zusammengesetzten Wörtern wird dadurch der Aufwand gigantisch. Bzw. die Wortliste dürfte garkeine zusammengesetzten Wörter enthalten, was eine sehr massive Einschränkung wäre und ausserdem wahrscheinlich von Hand sichergestellt werden müsste. Man kann ja nicht einmal eindeutig sagen wie ein Wort zusammengesetzt ist, z.B. Urinstinkt oder die berühmten Blumentopferde. Georg
Georg schrieb: > Anders > gesagt, muss man das Maximum an möglichen Wörtern finden? > > In Deutsch mit den nahezu beliebig zusammengesetzten Wörtern wird > dadurch der Aufwand gigantisch. Das würde ich als Variante des Rucksackproblems ansehen und damit wäre es NP-vollständig.
xyz schrieb: > wenn die Buchstaben sortiert sind, dann ist es überhaupt kein Problem. > Aber natürlich muss man alle Buchstaben einzeln prüfen. > > Die Frage ist nur wie man das tut. Wenn man z.B. nur die Buchstaben > a,A,b,B,c,C,...x,X,y,Y,z,Z nimmt, dann ist die Aufgabe einfach: > >
1 | > const char* words[] = { "ONE", "two", "three", "four", |
2 | > "FiVe", "six", "seven", "eight", |
3 | > "nine", "no1", "2no", "n30" }; |
4 | >
|
5 | > const size_t num_words = |
6 | > sizeof (words) / sizeof (*words); |
7 | >
|
8 | > for (size_t i = 0; i < num_words; i++) { |
9 | > bool is_valid = true; |
10 | >
|
11 | > for (size_t j = 0; j < strlen (words[i]); j++) { |
12 | > if (toupper (words[i][j]) < 'A' || |
13 | > toupper (words[i][j]) > 'Z') { |
14 | > is_valid = false; |
15 | > break; |
16 | > } |
17 | > } |
18 | >
|
19 | > if (is_valid) { |
20 | > printf ("yes:\t%s\n", words[i]); |
21 | > } |
22 | > else { |
23 | > printf ("no:\t%s\n", words[i]); |
24 | > } |
25 | > } |
26 | >
|
27 | >
|
28 | >
|
Da ist ein Fehler drin und muss korrekt lauten:
1 | const char* words[] = { "ONE", "two", "three", "four", |
2 | |
3 | "FiVe", "six", "seven", "eight", |
4 | |
5 | "niner", "no1", "2no", "n30" }; |
6 | |
7 | const size_t num_words = |
8 | |
9 | sizeof (words) / sizeof (*words); |
10 | |
11 | for (size_t i = 0; i < num_words; i++) { |
12 | |
13 | bool is_valid = true; |
14 | |
15 | for (size_t j = 0; j < strlen (words[i]); j++) { |
16 | |
17 | if (toupper (words[i][j]) < 'A' || |
18 | |
19 | toupper (words[i][j]) > 'Z') { |
20 | |
21 | is_valid = false; |
22 | |
23 | break; |
24 | |
25 | }
|
26 | |
27 | }
|
28 | |
29 | if (is_valid) { |
30 | |
31 | printf ("yes:\t%s\n", words[i]); |
32 | |
33 | }
|
34 | |
35 | else { |
36 | |
37 | printf ("no:\t%s\n", words[i]); |
38 | |
39 | }
|
40 | |
41 | }
|
Georg schrieb: > Bzw. die Wortliste dürfte garkeine > zusammengesetzten Wörter enthalten Warum nicht? Die Wortliste ist ja schon vorgegeben. Georg schrieb: > Soll z.B. ein Wort > wieder gestrichen werden, wenn sich herausstellt, dass man mit den > verbrauchten Buchstaben auch zwei andere Wörter bilden könnte? Anders > gesagt, muss man das Maximum an möglichen Wörtern finden? Diese Fragen sind schon wichtiger für eine mögliche Lösungsfindung
Rolf M. schrieb: > Hier sollen aber alle 100 Buchstaben der zweiten Datei verwendet werden. > Also wenn da 10 'A's vorkommen, dürfen die auch alle verwendet werden. > So interpretiere ich jedenfalls die Aufgabe Ich sehe ich hatte einen Fehler. Es sind maximal 26 Buchstaben in der Datei. Meistens aber ein Bruchteil vom deutschen Alphabet. Also zum Beispiel nur die Buchstaben [a b c u f o t]. Groß- und Kleinschreibung soll nicht unterschieden. Georg schrieb: > Wie intelligent soll denn der Algorithmus sein? Soll z.B. ein Wort > wieder gestrichen werden, wenn sich herausstellt, dass man mit den > verbrauchten Buchstaben auch zwei andere Wörter bilden könnte? Anders > gesagt, muss man das Maximum an möglichen Wörtern finden? Genau die Buchstaben "verschwinden" nicht wenn sie für ein Wort schon gebraucht wurden. Also soll die max Anzahl an möglichen Wörtern (die in einer Datei stehen) aus diesen Buchstaben gebildet werden.
jonas schrieb: > Genau die Buchstaben "verschwinden" nicht wenn sie für ein Wort schon > gebraucht wurden Das macht die Aufgabe sinnlos, bzw. es genügt wenn man alle 26 oder 29 Buchstaben nimmt, keine 100. Oder kommt jetzt wieder ein Salamischeibchen? Georg
jonas schrieb: > Rolf M. schrieb: >> Hier sollen aber alle 100 Buchstaben der zweiten Datei verwendet werden. >> Also wenn da 10 'A's vorkommen, dürfen die auch alle verwendet werden. >> So interpretiere ich jedenfalls die Aufgabe > Ich sehe ich hatte einen Fehler. Es sind maximal 26 Buchstaben in der > Datei. Das heißt, jeder Buchstabe des Alphabets kommt darin auch nur maximal einmal vor? > Genau die Buchstaben "verschwinden" nicht wenn sie für ein Wort schon > gebraucht wurden. Also darf ich jeden der Buchstaben beliebig oft einsetzen? Sprich: Wenn in der zweiten Datei 26 Buchstaben stehen, wäre das immer der Trivialfall, weil die erste Datei dann immer komplett damit gebildet werden kann, sofern sie nur aus Buchstaben und Leerzeichen besteht? > Also soll die max Anzahl an möglichen Wörtern (die in > einer Datei stehen) aus diesen Buchstaben gebildet werden. Georg schrieb: > Das macht die Aufgabe sinnlos, bzw. es genügt wenn man alle 26 oder 29 > Buchstaben nimmt, keine 100. Hat er ja auch geschrieben: jonas schrieb: > Ich sehe ich hatte einen Fehler. Es sind maximal 26 Buchstaben in der > Datei.
:
Bearbeitet durch User
Georg schrieb: > Das macht die Aufgabe sinnlos, bzw. es genügt wenn man alle 26 oder 29 > Buchstaben nimmt, keine 100. Habe ich ja über deinem Post geschrieben dass es immer weniger als 26 Buchstaben sind.
Rolf M. schrieb: > Das heißt, jeder Buchstabe des Alphabets kommt darin auch nur maximal > einmal vor? Genau, jeder Buchstabe kommt auch nur maximal einmal vor. Aber es kann sein das die Datei viel weniger Buchstaben hat als das Alphabet. Zm Beispiel nur 12 Buchstaben. Rolf M. schrieb: > Also darf ich jeden der Buchstaben beliebig oft einsetzen? So ist es! Rolf M. schrieb: > Sprich: Wenn in der zweiten Datei 26 Buchstaben stehen, wäre das immer > der Trivialfall, weil die erste Datei dann immer komplett damit gebildet > werden kann, sofern sie nur aus Buchstaben und Leerzeichen besteht? Jap, wobei das nicht vorkommen wird. Es sind meistens dann nur ein Bruchteil der Buchstaben aus dem Alphabet drin.
jonas schrieb: > Jap, wobei das nicht vorkommen wird. Es sind meistens dann nur ein > Bruchteil der Buchstaben aus dem Alphabet drin. Dann ist die Aufgabe aber trivial: man streicht einfach aus Liste 1 alle Wörter, die einen Buchstaben enthalten, der in der Liste 2 nicht vorkommt, und man ist in einem Durchgang fertig. Georg
Dann ist es doch extrem einfach. Man geht jeden Buchstaben jeden Wortes durch und sieht nach, ob er in der Tabelle ist. Wenn alle Buchstaben eines Wortes in der Tabelle stehen, kann das Wort gebildet werden. Bei sehr vielen Wörtern könnte man die auch nach dem ersten Buchstaben sortieren und alle Wörter rausschmeißen, deren erster Buchstabe nicht in der Tabelle steht. Dann das Gleiche mit jedem weiteren Buchstaben. Und wenn wir hier von 26 Buchstaben reden, muss man da auch nicht lange über Optimierungen nachdenken.
Dann sollte es doch recht einfach sein: Du gehst Datei 1 Wort für Wort durch und das jeweilige Wort wiederum Buchstabe für Buchstabe. Da schaust du nach, ob dieser in der Liste enthalten ist. Wenn nein, Abbruch und nächstes Wort. Wenn alle Buchstaben enthalten sind, merkst du dir das Wort. Dazu würde ich mir die Buchstaben in einem Set merken. In Python geht das recht kurz: (ein Python-Profi wird's sicherlich noch schöner hinbekommen)
1 | wörter=["hallo", "welt", "wie", "geht", "es"] |
2 | buchstaben=set("abcdehlotw")
|
3 | output = list() |
4 | for wort in wörter: |
5 | for buchstabe in wort: |
6 | if not buchstabe in buchstaben: |
7 | break |
8 | else: |
9 | output.append(wort) |
10 | print(output) |
:
Bearbeitet durch User
hier mal wie bei scrabble unter Berücksichtigung der Buchstabenanzahl
1 | from collections import defaultdict |
2 | |
3 | words = ['Hund', 'Pfund', 'Schund', 'rund', 'bunt', 'und', 'Lund', 'Nudel', 'Nuddel'] |
4 | letters = 'DNUHPLEX' |
5 | |
6 | |
7 | words = [word.lower() for word in sorted(words)] |
8 | letters = letters.lower() |
9 | |
10 | |
11 | def _count_letters(word): |
12 | result = defaultdict(lambda: 0) |
13 | for letter in word: |
14 | result[letter] += 1 |
15 | return result |
16 | |
17 | letters_counted = _count_letters(letters) |
18 | |
19 | def _in(word_counted, letters_counted): |
20 | for word_letter, letter_count in word_counted.items(): |
21 | if letters_counted[word_letter] < letter_count: |
22 | return False |
23 | return True |
24 | |
25 | words_valid = [_in(_count_letters(word), letters_counted) for word in words] |
26 | |
27 | for valid, word in zip(words_valid, words): |
28 | if valid: |
29 | print(word) |
:
Bearbeitet durch User
1 | #!/bin/sh
|
2 | |
3 | if [ $# != 1 ]; then echo "usage: $0 search <wordlist.txt"; exit 1; fi |
4 | |
5 | sortletters(){ printf "%s" "$1" | sed 's/./\0\x0/g' | sort -z | tr -d '\0'; } |
6 | |
7 | needle="$(sortletters "$1")" |
8 | while read word |
9 | do if [ "$needle" = "$(sortletters "$word")" ]; then echo "$word"; fi |
10 | done
|
M.E. hat der TO Jonas noch keine sinnvolle Definition seines Problems geliefert. Die erste Datei ist klar, Liste von Wörtern. Großschreibung ignoriert. Richtig? Bei der zweiten sind es Mal Buchstaben, Mal Wörter. Mal sind es 100, Mal darf jeder Buchstabe beliebig oft verwendet werden. Sinn macht es nur, wenn es Wörter sind, und aus jedem Wort einzeln die Buchstaben genommen werden. Und dann prüfen, welche Worte der ersten Datei sich damit leben lassen.
Falls es am Ende egal ist, wie oft ein Buchstabe verwendet wird: Jedes Wort in eine 32bit-zahl im Array W[1000] umwandeln, wo das erste Bit a, das zweite b usw. ist. Dann die erlaubten Buchstaben ebenso in eine 32bit Zahl T wandeln. Dann über das Array testen, wo T|W[i]==W[i] ist Da lohnt sich vermutlich keine Optimierung ohne weitere Infos
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.