Programmierübung erweitert "Wechstaben-verbuchsler" (aus Buchstabensammlung mache sinnvolles Wort)

[wira]

Hallo

Ich möchte die Aufgabenstellung aus https://www.fachinformatiker.de/topic/161467-programmier%C3%BCbung-wechstaben-verbuchsler-aus-buchstabensammlung-mache-sinnvolles-wort/?_fromLogin=1 erweitern.

Aus den gegebenen Buchstaben (z.B.  "aahrstu" )  soll nun auch Teilmengen gefunden werden, z.B. "Haus" und "Rat" und andere,

aber jeder Buchstabe darf nur so oft verwendet werden wie im Ausgangs"wort" vorhanden.

"Tat" wäre also kein erlaubtes Ergebnis, weil das "t" nur einmal im Ausgangs"wort" vorhanden.

Es geht mir um das Programmieren, bin mehr ein FI-SI.

Wie würdet ihr daran gehen?

Tschüss

[Mackenzie]

Ich würde mir mal das Thema Tries ansehen. Eine Datenstruktur speziell für Zeichenketten, die dabei noch eine gute Laufzeit hat.

[Whiz-zarD]

Ich würde wieder die Wortliste laden und jedes Wort nach der Anzahl der Buchstaben analysieren und dies dann mit den vorgegebenen Buchstaben vergleichen. Beispiel:

Wörter:
    Hose
        e   1
        h   1
        o   1
        s   1
        
    Rose
        e   1
        o   1
        r   1
        s   1

Buchstaben: 
    SEO
        e   1
        o   1
        s   1

vor 18 Minuten schrieb Mackenzie:

Ich würde mir mal das Thema Tries ansehen. Eine Datenstruktur speziell für Zeichenketten, die dabei noch eine gute Laufzeit hat.

Damit kommt man nicht weit, da ein Trie nur lexikalisch die Wörter speichert. Mit dem Buchstaben "SEO" könntest du nicht z.B. die Wörter "Hose" oder "Rose" herausfinden. 

[KeeperOfCoffee]

Mal ein Anfang basierend auf @Whiz-zarD Vorschlag

List<Dictionary<char, int>> charCount = new List<Dictionary<char, int>>();
woerterliste.ForEach(o => charCount.Add(o.GroupBy(c => c).Select(
                      c => new { Key = c.Key, Count = c.Count() }).ToDictionary(
                      Key => Key.Key, Count => Count.Count)));

danach kannst du recht einfach Prüfen, ob ein Wort zu den gegebenen Anforderungen passt.

Bearbeitet 9. Oktober 2019 von KeeperOfCoffee

[wira]

ich verstehe den Ansatz von KeeperOfCoffee nicht,

ich würde da mehrere Durchläufe planen für ein siebenbuchstabiges Wort,

erstmal dreibuchstabiges Wörterbuch prüfen, dann vierbuchstabiges Wörterbuch, dann ...

?

[Whiz-zarD]

@KeeperOfCoffee hat im Grunde nur meine Idee der Datenstruktur in Code umgesetzt. Beispiel:

Du hast die Buchstaben "aahrstu" angegeben. Du musst also die Buchstaben zählen und die Anzahl der Buchstaben pro Buchstabe darstellen. Dafür bietet sich ein Dictionary an, was dann so aussieht:

a => 2
h => 1
r => 1
s => 1
t => 1
u => 1

Nun durchläufst du alle Wörter und jedes Wort analysierst du ebenfalls auf die selbe Art und Weise, wie die angegebenen Buchstaben. Beispiel "Haus":

h => 1
a => 1
u => 1
s => 1

Nun musst du beide Dictionaries miteinander vergleichen und zwar dürfen in dem Wort nur Buchstaben vorkommen, die man angegeben hat und zusätzlich darf die Anzahl der Buchstaben nicht der angegebenen Buchstaben überschreiten.

ich hatte heute in der Bahn einige Stunden Zeit gehabt und hab die Aufgabe fertig. Ich wollte sie jetzt aber nicht präsentieren, da du die Aufgabe für dich selbst gestellt hast und ich es schade finden würde, wenn jemand vor dir die Lösung präsentieren würde.