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"
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:
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:>>
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.
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)
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
Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.
Wichtige Regeln - erst lesen, dann posten!
Groß- und Kleinschreibung verwenden
Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang