Alle Strings bis zu einer Maimallänge aufzählen, die Bedingung erfüllen

[berndoa]

Hallo, mich beschäftigt geistig nahc wie vor die Frage wie man so Aufgaben bearbeitet (ohne Rekursion) wo man im Prinzip systematisch immer lägnere Strings (Oder Zahlen oder so) finden muss, die bestimmte Kriterien erfüllen.

Und dabei erst eine viel zu große Sammlung an Strings zu bauen, aus der man die unpassend darin platzierten Strings rauswirft.

Nun hat mir da ChatGPT eine Idee gegeben, die vielleicht etwas dumm ist aber funktioneiren könnte.

Sagen wir mal, wir suchen alle Strings der Länge <=20, die maximal 3 mal ein a enthalten.

Nun könnte man alle Strings der Länge <=20 bilden und da die sehr vielen unpassenden wieder rauswerfen.
Wollen wir aber nicht.

Nach etwas Blabla mit ChatGPT schlug der mir in etwa diese Vorgehensweise vor, die meiner Empfiundung nahc stark an Breitensuche erinnert:
Man habe erst mal eine anfangs leere Ergebnisliste.
Hier kommen alle Strings rein, die unseren bedingungen genügen.

Nann noch 1-2 Stringlisten, wo wir temporär Strings unterbringen und wieder rausschmeissen.
nenne wir die 2 Hilfslsiten A und Bm, die anfangs ebenso leer sein sollen.

Nun müssten wir folgendes machen können:
Zu Beginn fügen wir den leeren string zu B hinzu.

danahc kopieren wir den Inhalt von B zu A .
wir löschen den inhalt von B.
Wir gehen nun der reihe nahc alle Strings in A durch:
ist ein String aus A ein korrekter String (erfüllt die anforderungen), dann fügen wir ihn zur ergebnisliste hinzu.
ist der string in A ein nicht-korrekter string, so bilden wir alle kombinationen aus diesem string und einem buchstaben des alphabeten und fügen es zu b hinzu.
(Falls die Strings in A bereits maximallänge haben, wird natürlich kein noch längerer string gebaut)

sobald wir alle strings in A durchgeguckt haben, leeren wir A.
(wir haben also alle guten strings aus A in die ergebnislsite verschoben und die schlechten string dazu genutzt, nächstlägnere strings in B zu bauen, die vielleicht noch zu guten strings führen könnten).

rinse and repeat, nun im Prinzip.
alle strings der länge 1 in A werden durchgeguckt, "fertige" Strings kommen zur ergenislsite, unpassende Strings werden vor dem löschen dazu genutzt strings der nächsten länge in B zu bauen.

was maximallänge erreicht hat, ist entweder ein ergebnisstring oder landet kommentarlos im müllkorb.

So müsste das funktionieren, oder?
dass man also in einer dummylsite so die zwischenergebnisse der aktuellen stufe hält, die auf korrektheit prüft und nicht-korrekte strings zum bauen der nächsten dummyliste nutzt.

so müsste man so ein problem recht easy mit einer passenden while loop (mit bedingung der art wie "Strings in A haben länge <=20" oder so)
lösen können, oder?

Hintergrund für die frage sind keine easy stringspielereien sondern es geht mir um das bauen aller möglichen kombinationen beim blackjack.
wo man nicht so easy gerade mal alle möglichen endzustände auszählen kann, weil da je nahc glück sehr viele karten gezogen werden können )

 

[mihe7]

Frage: warum ohne Rekursion?

 

[berndoa]

Um das typische Problem mit der Rekursionstiefe zu vermeiden.
Klar macht es bei Strings mit Länge 20 oder so keine Probleme.
Aber wenn ich bspw. Strings der Länge 20000 oder sows machen will, könnte es da ggbfls. eng werden.

Und generell ist es mir vom Vorgehen her auch lieber so dass ich es wie hier in eienr Art breitensuche (erst alle Strings der Länge 0, dann Länge 1, etc.) mache,
als dass durch 20 verschachtelte Rekursionen, wenn man sichs in nem Baum/Verzweigungsdiagramm so vorstellt, ein Pfad Ewigkeiten nach unten gegangen wird bevor es an den nächsten geht (was dann mehr so wie Tiefensuche wäre).

Ist halt einfahc praktischer, schätze ich.

Bei meinem Blackjack Spiel hätte ich bspw. auch gar nicht gewusst wie ich das so richtig mit Rekursion hinkriege.
Während es reht easy ist, gegeben ein bestimmter Spielzustand, durch Anwenden der nun legitim möglichen Schritte eine Runde weiterzugehen.

Klar, ginge auch rekursiv.
Aber keine Ahnung, so kann ich mirs neinfach besser vorstellen
ist einfach mehr eine Sache des Geschmacks, sowie halt zum Rekursion vermeiden.
Steige meistens bei Rekursion, wenns gar noch in einer Methode mehrere Aufrufe derselben gibt, nicht mehr durch.

Kapiere in dem Zusammenhang nicht mal wirklich das 0815 Standardbeispiel, die Rekursionsmethode für die Türme von Hanoi.

Vermeide eifnahc gern Rekursion

 

[mihe7]

Kapiere in dem Zusammenhang nicht mal wirklich das 0815 Standardbeispiel, die Rekursionsmethode für die Türme von Hanoi.

Das Spiel ist auch nicht einfach.

Und generell ist es mir vom Vorgehen her auch lieber so dass ich es wie hier in eienr Art breitensuche (erst alle Strings der Länge 0, dann Länge 1, etc.) mache,
als dass durch 20 verschachtelte Rekursionen, wenn man sichs in nem Baum/Verzweigungsdiagramm so vorstellt, ein Pfad Ewigkeiten nach unten gegangen wird bevor es an den nächsten geht (was dann mehr so wie Tiefensuche wäre).

Rekursion macht in erster Linie dann Sinn, wenn man Rückgriff auf vorherige Zustände braucht oder man rekursive Strukturen hat. Ohne Rekursion muss man in solchen Fällen ggf. einen Stack bemühen.

Da der leere String den Anforderungen genügt, endet Dein Algorithmus mit diesem als Ergebnis (er ist korrekt, also wird kein längerer String gebaut).

Aber wenn ich bspw. Strings der Länge 20000 oder sows machen will, könnte es da ggbfls. eng werden.

Wenn Du Strings der Länge 20000 haben willst, dann hast Du ein anderes Problem.

 

[berndoa]

War jetzt nur ein Beispiel.

Jedenfalls steige ich bei was Iterativem meistens wesentlich eifnacher durch als bei Rekursivem, insofenr bevorzuge ich das da.

Bspw. so Anweisungen wie
"Ziehe Karten solange bis die Kartensumme mod 11 >7 ist, dann zieht B nach gewissen Regeln Karten, dann zieht A weitere Karten gemäß weiterer Regeln"

Da eine rekursive MEthode zu bauen die irgendwie berücksichigt wie wo wan wir gerade sind im Zusammenbauen, schwierig.

ich bin jedenfalls kein großer Fan von Rekursion und vermeide es wo auch immer möglich

 

[mihe7]

Bleiben wir mal bei Deinem Buchstabenbeispiel. Im Endeffekt willst Du Wörter (Kombinationen) der Länge n bilden. Ein solches Wort besteht aus einem (n-1) Zeichen langen Präfix und einem daran angefügten Buchstaben. Nimmt man an, dass das Präfix ein Wort ist, dass den gestellten Anforderungen genügt, können diese nur durch den anzufügenden Buchstaben verletzt werden.

Man könnte also eine Methode schreiben, die einen Präfix entgegennimmt und an diesen einen Buchstaben anfügt. Dabei kann schon der Präfix dahingehend untersucht werden, ob/welche zusätzlichen Buchstaben die Anforderungen verletzen.

public List<String> buildWords(String prefix, List<String> fullAlphabet) {
    List<String> alphabet = fullAlphabet;
    if (count(prefix, 'a') == 3) {
        alphabet = fullAlphabet.stream().filter(letter -> !letter.equals("a")).toList();
    }

    List<String> result = new ArrayList<>();
    for (String letter : alphabet) {
        result.add(prefix + letter);
    }
    return result;
}

private int count(String word, char letter) {
    return (int) word.chars().filter(ch -> ch == letter).count();
}

Wenn wir also mit einem leeren String und dem Alphabet "a", "b" und "c" beginnen:

jshell> System.out.println(buildWords("", List.of("a","b","c")))
[a, b, c]

Das sind nun die Wörter der Länge 1. Um die Wörter der Länge 2 zu erhalten, müsste man die Methode für jedes dieser Wörter erneut aufrufen:

jshell> System.out.println(buildWords("a", List.of("a","b","c")))
[aa, ab, ac]

jshell> System.out.println(buildWords("b", List.of("a","b","c")))
[ba, bb, bc]

jshell> System.out.println(buildWords("c", List.of("a","b","c")))
[ca, cb, cc]

Um die Wörter der Länge 3 zu erhalten, müsste man die Methode für jedes dieser Wörter erneut aufrufen usw.

Also, Schleife drumherum:

public List<String> allWords(int maxLength) {
    List<String> alphabet = List.of("a", "b", "c");
    List<String> words = new ArrayList<>();
    words.add("");
    List<String> prefixes = words;

    for (int i = 0; i < maxLength; i++) {
        List<String> newWords = new ArrayList<>();
        for (String prefix : prefixes) {
            newWords.addAll(buildWords(prefix, alphabet));
        }
        words.addAll(newWords);
        prefixes = newWords;
    }

    return words;
}

 

[KonradN]

Generell lässt sich das Problem in zwei Phh eh obleme unterteilen:
A) die generierung belobiget Zeichenfolgen mit einer bestimmten Länge. Dabei ist im Alphabet kein a.

B) in ein gegebenen String eine bestimmte Menge a unterbringen

Also ein String mit 20 Zeichen und davon 3 a ist zurückgeführt auf einen String mit 17 Zeichen ohne a und dann 3 a hinzugefügt.

 

[mihe7]

Generell lässt sich das Problem in zwei Phh eh obleme unterteilen:

Ja, dieses spezielle Problem schon. Wenn die Anforderungen komplexer werden, dann dürfte sich das aber schwierig gestalten.

Also ein String mit 20 Zeichen und davon 3 a ist zurückgeführt auf einen String mit 16 Zeichen ohne a und dann 3 a hinzugefügt.

 

[KonradN]

Ich habe andere den Thread schlicht nicht richtig gelesen, da mir das alles etwas konfus vorgekommen ist. Alle Möglichkeiten zu generieren erscheint nicht sinnvoll.

Auch das mit den 20000 ist ein Witz: wie viele Kombinationen sollen da denn erstellt werden? Generell ist Rekursion da kein Problem. Selbst bei 2.000.000 Zeichen nicht. Denn das gibt ja nur die Tiefe der Aufrufe wieder. 2.000.000 Aufrufe - mal angenommen pro Aufruf wären 1000 Byte notwendig, dann wäre man bei 2GB Stack …. Wir sind also noch in einem Bereich, der möglich ist.

Nur wie viele Kombinationen sollen denn da generiert werden? Die wachsen ja nicht linear. Also selbst wenn du die auf die Platte schreibst dürfte die Platte zu klein sein. Wie viele Elemente generierst du pro Sekunde? Auch der Zeitbedarf ist vermutlich kritisch.

Das ist wie bei der Idee, der alle Kombinationen eines Byte-Arrays durchgehen wollte …. Nur dass da die Möglichkeiten weit über Anzahl der Atome im Universum war (also die Zehnerpotenz war deutlich größer)

Die Frage ist, was man genau will. Einzelne Werte berechnen: der Ansatz mit der Aufteilung dürfte einfach sein.
Mathematische Berechnungen a.la. Sowie viele Möglichkeiten gibt es: dürfte darüber auch gehen.

 

[KonradN]

Ja, am Smartphone ist es schwer zu tippen …. Da kommt statt einer 17 leicht eine 16 …. Und da die Schrift so klein ist, ist das auch nicht wirklich noch einmal verifiziert.

 

[httpdigest]

@berndoa : Erstmal beschreibst du hier ein sehr allgemeines Problem: "Finde alle Strings der Länge <= n, welche eine bestimmte Bedingung erfüllen."

Das geht schon ziemlich in Richtung theoretischer Informatik und formale Sprachen, denn im allgemeinen kann das ja formuliert werden als:
Zähle die Menge/Sprache L = { w | w ∈ Σ⁺ , |w| <= n , P(w) } auf.
Also alle "Wörter" w über einem Alphabet Σ mit den geforderten Eigenschaften, die das Prädikat P(w) erfüllen.

Und theoretisch kann P(w) ja ein beliebiges Prädikat sein, wie etwa: "w ist ein Programm (in einer beliebigen Programmiersprache), deren Ausführung in endlicher Zeit hält."

Also: Grundsätzlich ist P(w) erstmal nicht entscheidbar, geschweige denn L aufzählbar. Es existiert im Allgemeinen also kein Algorithmus bzw. Vorgehensweise, der/die L aufzählen kann.

Nun zu deinem speziellen P(w) mit: "Es kommt in w höchstens 3 mal ein 'a' vor."

Das wiederum ist entscheidbar und aufzählbar. Aber eben auch wieder nicht algorithmisch sondern mit Intellekt, Einfallsreichtum/Fantasie. Das ist quasi die Essenz dessen, was Informatik ausmacht und warum Informatiker nicht durch einen Algorithmus bzw. eine KI abgelöst werden können.

Im Endeffekt muss hier durch Ausprobieren und Nachdenken eine Grammatik gefunden werden, die Wörter aus L (und nur L) generieren kann. Und es gibt auch keinen Algorithmus, der für eine solche Sprache bzw. Menge L automatisch solch eine Grammatik findet, geschweige denn, dir die Form der Grammatik (siehe z.B. Chomsky Hierarchy) bestimmt. Die "Form" von L wird dadurch bestimmt, dass jemand eine Grammatik dieser Form findet, welche L generiert und einen Automaten findet, welcher L akzeptiert.

Du musst dich letztlich also für jedes spezielle P(w) hinsetzen, und nachdenken, wie eine Grammatik (bzw. letztlich Programm) aussehen könnte, die L generiert.

 

[berndoa]

Wow, das klang jetzt hoch philosophishc und sichelrich richtig, hilft nur konret jetzt nicht so viel.

Klar, irgendwie kann man vielleicht zu nem Problem auch ne Grammatik bauen (welcher Stufe die dann ist ob regulär, kontextfrei, etc. sei mal hingestellt).


Mir gings halt einfach nur generell um das Prinzip, was im kern rekursives irgendwie iterativ hinzukiregen um eben Probleme mit dr Rekursionstiefe zu vermeiden.
WO man halt einfach systematisch der Reihe nach alle Möglichkeiten für Strings oder andere Reihen an Objekten baut.

Wie im Blackjack und Co. bspw. wo man irgendwie zwischen 2 und fast unendlich Karten ziehen kann und mit jeder gezogenen Karten man entweder näher an der Gewinnbedingung dran ist (Kartenwert<=21, kartensumme größer als die vom Dealer) oder verloren hat (weil kartensumme>21).
Ob man eine weitere Karte zieht und auch ziehen darf, hängt von Randbedingungen ab sowei auch rein eine Entshceidung des Spielers.

Wie will man da alle möglichen Szenarien aufzählen?

Systematisch wäre natürlich, Szenarien immer größer werdender Endkartenzahl zu gucken.
Also wenn man die Szenarien mit 2 Spielerkarten hat, welche Szenarien kann draus bauen wenn der Spieler eine weitere Karte zieht?

Wäre was rekursives shcon naheliegend.

Gleichzeitig darf man aus Szenarien, die einen Endzustand darstellen (Spieler hat gewonnen oder verloren, also keine weitere Aktion mehr nötig da Spiel zuende),
nicht durch "ich zieh noch eine weitere karte" andere Szenarien bauen, die real iM Rahmen der Regeln gar nicht passieren können.

Dann kann man natürlich jedem legitimen Szenario noch eine Geschehenswahrshceinlichkeit zuordnen (mit oder ohne Kartenzählen)
sowie natürlich wer das Szenario gewonnen hat.

Das rekursiv geht sicherlich, aber halt unschön.
Weil bei jedem inneren Aufruf der Funktion ja geguckt werden muss, was schon in den äusseren Aufrufen passiert ist.
Müsste man irgendwelche Parameter übergeben und so, wird umständlich.

 

[httpdigest]

Bezüglich: Rekursionstiefe ist ein Problem --> ist es nicht. Wird es für keinen praktischen rekursiven Algorithmus sein. Du solltest aufhören, deine Zeit damit zu verschwenden, zwanghaft nach iterativen Lösungen zu suchen, wenn sich eine rekursive Lösung bietet.
Und falls die Rekursionstiefe bzw. der Thread-Stack-Speicher zu klein sein sollte, dann kannst du die JVM immer noch anweisen, mehr Stack-Speicher pro Thread zu alloziieren mit dem JVM-Parameter -Xss (z.B. mit -Xss128m oder wieviel du auch immer brauchst).

 

[Marinek]

Bezüglich: Rekursionstiefe ist ein Problem --> ist es nicht. Wird es für keinen praktischen rekursiven Algorithmus sein

Also die Fibbonacci Folge ist zunächst eine Rekusrion: der Form fn = f(n-1) + (n-2);

Hier ist die iterative Form wesentlich Speicherfreundlicher als die rekursive Variante. Mithin lohnt es sich schon nach einer Variante zu suchen. Bin jetzt kein Profi der theoretischen Informatik, und habe auch nicht den Thread nicht im Detail verfolgt.