Aus X Buchstaben Y Wörter bilden - Programmieren

[jonas (Gast)]

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.

[Christoph db1uq K. (christoph_kessler)]

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"

[jonas (Gast)]

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.

[Rainer S. (enevile)]

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.

[Willi (Gast)]

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 ?

[Rolf M. (rmagnus)]

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.

[Dussel (Gast)]

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 (Gast)]

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.

[xyz (Gast)]

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:

   const char* words[] = { "ONE",  "two", "three", "four",
                           "FiVe", "six", "seven", "eight",
                           "nine", "no1", "2no",   "n30" };

   const size_t num_words =
      sizeof (words) / sizeof (*words);

   for (size_t i = 0; i < num_words; i++) {
      bool is_valid = true;

      for (size_t j = 0; j < strlen (words[i]); j++) {
         if (toupper (words[i][j]) < 'A' ||
             toupper (words[i][j]) > 'Z') {
            is_valid = false;
            break;
         }
      }

      if (is_valid) {
         printf ("yes:\t%s\n", words[i]);
      }
      else {
         printf ("no:\t%s\n", words[i]);
      }
   }

[jonas (Gast)]

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.

[Rolf M. (rmagnus)]

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.

[Georg (Gast)]

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

[Dussel (Gast)]

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.

[Nano (Gast)]

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:
>
>

>    const char* words[] = { "ONE",  "two", "three", "four",
>                            "FiVe", "six", "seven", "eight",
>                            "nine", "no1", "2no",   "n30" };
> 
>    const size_t num_words =
>       sizeof (words) / sizeof (*words);
> 
>    for (size_t i = 0; i < num_words; i++) {
>       bool is_valid = true;
> 
>       for (size_t j = 0; j < strlen (words[i]); j++) {
>          if (toupper (words[i][j]) < 'A' ||
>              toupper (words[i][j]) > 'Z') {
>             is_valid = false;
>             break;
>          }
>       }
> 
>       if (is_valid) {
>          printf ("yes:\t%s\n", words[i]);
>       }
>       else {
>          printf ("no:\t%s\n", words[i]);
>       }
>    }
> 
> 
>

Da ist ein Fehler drin und muss korrekt lauten:

   const char* words[] = { "ONE",  "two", "three", "four",

                           "FiVe", "six", "seven", "eight",

                           "niner", "no1", "2no",   "n30" };

   const size_t num_words =

      sizeof (words) / sizeof (*words);

   for (size_t i = 0; i < num_words; i++) {

      bool is_valid = true;

      for (size_t j = 0; j < strlen (words[i]); j++) {

         if (toupper (words[i][j]) < 'A' ||

             toupper (words[i][j]) > 'Z') {

            is_valid = false;

            break;

         }

      }

      if (is_valid) {

         printf ("yes:\t%s\n", words[i]);

      }

      else {

         printf ("no:\t%s\n", words[i]);

      }

   }

[Operator S. (smkr)]

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

[jonas (Gast)]

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.

[Georg (Gast)]

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

[Rolf M. (rmagnus)]

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.

[jonas (Gast)]

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.

[jonas (Gast)]

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.

[Georg (Gast)]

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

[Dussel (Gast)]

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.

[Rolf M. (rmagnus)]

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)

wörter=["hallo", "welt", "wie", "geht", "es"]
buchstaben=set("abcdehlotw")
output = list()
for wort in wörter:
    for buchstabe in wort:
        if not buchstabe in buchstaben:
            break
    else:
        output.append(wort)
print(output)

[A. S. (rava)]

hier mal wie bei scrabble unter Berücksichtigung der Buchstabenanzahl

from collections import defaultdict 

words = ['Hund', 'Pfund', 'Schund', 'rund', 'bunt', 'und', 'Lund', 'Nudel', 'Nuddel']
letters = 'DNUHPLEX'


words = [word.lower() for word in sorted(words)]
letters = letters.lower()


def _count_letters(word):
    result = defaultdict(lambda: 0)
    for letter in word:
        result[letter] += 1
    return result

letters_counted = _count_letters(letters)

def _in(word_counted, letters_counted):
    for word_letter, letter_count in word_counted.items():
        if letters_counted[word_letter] < letter_count:
            return False
    return True

words_valid = [_in(_count_letters(word), letters_counted) for word in words]

for valid, word in zip(words_valid, words):
    if valid:
        print(word)

[🐧 DPA 🐧 (Gast)]

#!/bin/sh

if [ $# != 1 ]; then echo "usage: $0 search <wordlist.txt"; exit 1; fi

sortletters(){ printf "%s" "$1" | sed 's/./\0\x0/g' | sort -z | tr -d '\0'; }

needle="$(sortletters "$1")"
while read word
  do if [ "$needle" = "$(sortletters "$word")" ]; then echo "$word"; fi
done

[A. S. (achs)]

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.

[A. S. (achs)]

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