Liste aller Kombintionen mit Einschränkungen

[berndoa]

Hallo,
ich hätte mal eien Frage:
Mir ist beim Lesen einer anderen Frage hier (Die Frage mit dem links/rechts weg abweichen) dass ich eine bestimmte Art Aufgaben einfach nicht zu lösen im Stande bin:
Wenn ich bspw. wie bei der anderen Frage n Mal den Buchstaben "R" und n Mal den Buchstaben "L" habe
(n sei irgendeine ganze Zahl)
und alle Kombinationen dieser 2*n Buchstaben finden/auflsiten soll sodass aber bspw. wenn man von links nahc rechts diesen String durchgeht,
zu keinem Zeitpunkt mehr R als L gekommen sind.

Also mit n=3 wäre bspw. LLRLRR in Ordnung.

LRRLLR wäre hingegen nicht in Ordnung denn:
Gehen wir von links durch kommt erst ein L und dann aber 2 R.
wenn wir L +1 zuordnen , R -1 zuordnen und von links nach rechts durchgehen, stehen wir nahc 3 Zeichen bei
+1-1-1=-1 was <0 ist, also mehr R als L und das ist unzulässig.
Daher ist LRRLLR kein zulässiger String.

War jetzt ein Beispiel.

Frage wäre wie ich bspw. für n=3 die Kombinationen finde.

Primitive Vairante wäre, einfach ALLE Kombinationen aus 3 L und 3 R in nem Array oder so zu sammeln und dnan abr wieder alle zu kicken die die bedingung nicht erfüllen.

Kann man machen aber wenn wir bspw. n=50 haben, wird die Lsite schon extrem riesig.
was ja per se unnötig ist, so eine große Lsite zu haben um sie dann auf den bruchteil der "legalen" Strings wieder zusammenzuschrumpfen.

Aber wie findet man "klug" alle Strings?

Ich könnte mir da, bisher aber nur als grobe Idee, eine rekursive Funktion vorstellen, die das bewerkstelligen könnte irgendwie.

public class Test{
    int maxlength=6;//=2*n

    public String testmethode(String a){
        if(a.length==6){
            //a zu Ergebnisarray hinzufügen
        }
        if(/* a+"R" erfüllt Bedingung */){
            testMethode(a+"R");
        }
        if(/* a+"L" erfüllt Bedingung */){
            testMethode(a+"L");
        }

    }

}

So in etwa, so grob der Gedanke (habe das gerade nach zig Woche nohne Javaprogrammieren gerade im Editor geschrieben, übernehme also null verantwortung für fehler)

Problem nur:
ist maxlength bspw. 2000 oder so, dann scheitert es, wie immer bei rekursion, an der relativ niedrigen maximalen rekursionstiefe.

rekursiv ist also nicht.

Explizit?
Aber wie?

fiele mir nur wieder ein, alle kombinationen der reihe nahc zu erzeugen, bei jeder ezreugten kombi zu gucken ob sie dne regeln entspricht und falls ja hinzufügen.

aber eine ecplizite variante, die erst gar nicht unnötig unzulässige kombinationen baut, die dann wieder geprüft und verworfen werden müssen, fällt mir nicht ein.

zumal mir auch kein guter Datentyp einfällt um überhaupt die "legalen" lösungen zu speichern, sodass da immer mehr dazu kommen können im laufe der suche.
Arraylist oder so vielleicht?



oder ein anderes Problem das im groben das selbe grundproblem für mich darstellt:
Es werde ein spiel gespielt wo jemand einen würfel wirft.
es wird so lange immer wieder gewürfelt bis derjenige (eine 5 würfelt oder die summe des letzten, 3.letzten und 5.letzten wurfes zusammen <7 ergibt).

es gäbe noch die einshcränkung dass maximal 20 mal gewürfelt wird, no matter what.


frage wäre nun alle möglichen würfelfolgen aufzulisten.
12345 wäre in der liste
162316 wäre da drin (weil hier 1+2+1<7 ist).

es gäbe auch sichelrich strings der länge 20 und auch kleinere, also alles bunt gemischt.

wie würde man das sinnvoll angehen?

ganz naiv könnte man, da ja maximal 20 würfe, ALLE komninationen aus zahlen 1-6 und bis zu 20 mal "ziehen" machen.
was aber eine unaussprechlich lange lsite werden würde (zu lang für java).
und dann würde man 95% der sachen rausschmeissen wieder.
also sehr ineffizient.

Wie würde man das klug lösen? (rekursion geht ja wegen rekursionstiefe nicht, wenns mal längere strings sein dürfen).

 

[httpdigest]

Ich würde das Problem tatsächlich erst einmal rekursiv lösen (recht einfach) und dann den rekursiven Algorithmus in einen iterativen umwandeln.
Um das Problem, dass die Rekursion aufgrund der begrenzten Stacktiefe nicht weit genug geht, würde ich mir erstmal keine Sorgen machen.
Du wirst feststellen, dass du selbst bei Längen von n = 1000 (also Strings der Länge 2000) keine Probleme haben wirst mit der Stacktiefe bei einer normalen JVM unter x64 ohne spezielle JVM-Argumente.
Wenn du die rekursive Lösung hast, dann kannst du einen ganz einfachen Algorithmus anwenden, um sie in eine iterative Lösung umzuwandeln, nämlich, in dem du die Stackframes der Methoden (die Argumente und Methodenaufrufe) selbst in einer dynamischen Listenstruktur (z.B. Stack oder Queue) speicherst und iterativ abarbeitest.

 

[httpdigest]

Hier schonmal ein Denkanstoß für eine rekursive Lösung:

Spoiler

public static void rec(int n) {
  // beginne immer mit einem "L" und einem "R"-Budget von 1
  rec(n, 1, 1, "L");
}
private static void rec(int n, int numL, int rBudget, String soFar) {
  // Falls wir am Ende des zu erzeugenden Strings sind, printe ihn aus
  if (n * 2 == soFar.length()) {
    System.out.println(soFar);
    return;
  }

  // Haben wir genug Budget, um nun ein "R" zu generieren?
  if (...) // <- hier muss eine einfache Bedingung hin
    // Generiere ein "R" und verringere das Budget zum Generieren eines "R"s
    ...; // <- hier muss eine Codezeile hin

  // Können wir ein "L" generieren, ohne, dass die Anzahl der Ls zu groß wird?
  if (...) // <- hier muss eine einfache Bedingung hin
    // Generiere ein "L" und erhöhe das Budget zum Generieren eines "R"s
    ...; // <- hier muss eine Codezeile hin
}

 

[MarvinsDepression]

Iterativ läßt sich das sicher auch umsetzen, wird aber weit weniger elegant aussehen. Eine rekusive Variante findest Du hier.

Spoiler: Wege zum Ziel

import java.util.LinkedList;

public class MyClass {
    
    static LinkedList<String> list = new LinkedList<>();
    static char[] path;
    
    public static void main(String args[]) {
        path = new char[8]; // only even numbers!
        
        buildPath(path.length, 0);
        
        System.out.println("Size of list: "+ list.size());
        for (var path : list) {
            System.out.println(path);
        }
    }
    
    static void buildPath(int stepsToGo, int currentStepsLeft) {
        if (stepsToGo <= 0) {
            list.add(new String(path));
            return;
        }
        
        if (stepsToGo > currentStepsLeft) {
            path[stepsToGo - 1] = 'L';
            buildPath(stepsToGo - 1, currentStepsLeft + 1);
        }
        if (currentStepsLeft > 0) {
            path[stepsToGo - 1] = 'R';
            buildPath(stepsToGo - 1, currentStepsLeft - 1);
        }
    }
}

Edit: mist, eine Minute zu spät...😣

 

[berndoa]

Ich würde das Problem tatsächlich erst einmal rekursiv lösen (recht einfach) und dann den rekursiven Algorithmus in einen iterativen umwandeln.
Um das Problem, dass die Rekursion aufgrund der begrenzten Stacktiefe nicht weit genug geht, würde ich mir erstmal keine Sorgen machen.
Du wirst feststellen, dass du selbst bei Längen von n = 1000 (also Strings der Länge 2000) keine Probleme haben wirst mit der Stacktiefe bei einer normalen JVM unter x64 ohne spezielle JVM-Argumente.
Wenn du die rekursive Lösung hast, dann kannst du einen ganz einfachen Algorithmus anwenden, um sie in eine iterative Lösung umzuwandeln, nämlich, in dem du die Stackframes der Methoden (die Argumente und Methodenaufrufe) selbst in einer dynamischen Listenstruktur (z.B. Stack oder Queue) speicherst und iterativ abarbeitest.

Den letzten Satz musst du mir nochmal erklären, den checke ich nicht so ganz 🙂

 

[berndoa]

Ich würde das Problem tatsächlich erst einmal rekursiv lösen (recht einfach) und dann den rekursiven Algorithmus in einen iterativen umwandeln.
Um das Problem, dass die Rekursion aufgrund der begrenzten Stacktiefe nicht weit genug geht, würde ich mir erstmal keine Sorgen machen.
Du wirst feststellen, dass du selbst bei Längen von n = 1000 (also Strings der Länge 2000) keine Probleme haben wirst mit der Stacktiefe bei einer normalen JVM unter x64 ohne spezielle JVM-Argumente.
Wenn du die rekursive Lösung hast, dann kannst du einen ganz einfachen Algorithmus anwenden, um sie in eine iterative Lösung umzuwandeln, nämlich, in dem du die Stackframes der Methoden (die Argumente und Methodenaufrufe) selbst in einer dynamischen Listenstruktur (z.B. Stack oder Queue) speicherst und iterativ abarbeitest.

Kannst du da vielleicht irgendwie ein einfaches Beispiel dazu machen oder so? 🙂

 

[KonradN]

Also erst einmal sehe ich die Problematik mit der Rekursionstiefe nicht. Bei n Elementen hast Du eine Tiefe von n Aufrufen. Und die Anzahl der Möglichkeiten steigt massiv an wen Du nur einen Aufruf dazu nimmst.

Und Du kannst jeden rekursiven Algorithmus in einen iterativen Umwandeln. Das sollte klar sein, denn unter dem Strich kann der Computer es nur iterativ abarbeiten. Du kannst also machen, was der Computer beim rekursiven Ablauf macht: Auf einem Stack eifnach alles ablegen, was Du an Parametern und lokalen Variablen brauchst. Aus den rekursiven Aufrufen wird dann nur eine Schleife, in der Du dann halt etwas auf den Stack legst ... und nach der Bearbeitung nimmst Du natürlich etwas vom Stack wieder runter.

Denn was passiert bei einem rekursiven Aufruf? Auf den Stack kommt:

• Rückgabe sofern vorhanden
• Rücksprungadresse - sprich: Wo geht es danach weiter?
• Parameter
• lokale Variablen

Dann läuft es durch und sobald es zu einem Return kommt, passiert:

• Lokale Variablen und Parameter werden vom Stack genommen (einfaches Umsetzen des Stackpointers, mit den Inhalkten passiert sonst nichts!)
• die Rücksprungadresse wird angesprungen
• Da wird dann das Ergebnis vom Stack genommen.

Du hast also vor dem Aufruf einen Zustand des Stacks und direkt nach dem Aufruf hast Du diesen Zustand wieder hergestellt.

 

[berndoa]

Während ich zwar den Gedanken dahinter verstehe, will mir noch nicht einleuchten wie man sowas praktisch umsetzt.

Kannst du mir bspw. sagen wie man folgende rekursive Funktion in was iteratives umwandelt ?
(Hoffe ich habe es gerade richig zusammengeschustert. Halt eine Methode die alle Strings der maximallänge 20 baut und druckt,
die die Symbole L und R beinhalten und wo egal wo im String man einen Schnitt macht, wo der linke Teilstring immer mehr oder gleich viele R als L enthält. Klar, budget hätte man auch statt als globale Varoiable immer mit aktuellem Wert beim Funktionsaufruf mit übergeben können, gäbs als 2 Funktionsparameter statt Einem.)

public class A{
    int maxLength=20;
    int budget=0;

    public static void Main(String[] args){
        builder("");
    }

    public void builder(String a){
        if(budget<0 || a.length>maxLength){return;}
        if(budget==0 && a.length<=maxLength){
            System.out.println(a)
        }


        //es wird ein L angefügt, welche das budget um -1 ändert
        budget=budget-1;
        builder(a+"L")
        budget=budget+1;

        //es wird ein R angefügt, welche das budget um +1 ändert
        budget=budget+1;
        builder(a+"R")
        budget=budget-1;
    }

   
   
   
}

 

[mihe7]

Bei einem Methodenaufruf wird ein Stackframe eingerichtet, der neben Platz für die lokalen Variablen auch Parameter und Rücksprungadresse enthält, dann wird an den Beginn der Methode gesprungen, die Methode wird ausgeführt und bei einer Rückkehr wird der Stackframe vom Stack genommen und an die Rücksprungadresse gesprungen.

Wenn man mal die Zeilennummern als Adresse verwendet, dann würde in Zeile 18 also die Zeile 19 als Rücksprungadresse und "a"+L als Parameter auf den Stack gelegt, anschließend wird an den Beginn der Methode gesprungen. Letzteres erreicht man mit einer Schleife, die natürlich endet, wenn der letzte Stackframe vom Stack genommen wurde, der Stack also leer ist.

In Deinem Code gibt es zwei Methodenaufrufe also auch zwei Rücksprungadressen, einmal Zeile 19 und einmal Zeile 24. Das muss man sich natürlich merken.

    static record Params(String word, int budget, int nextStep) {}

    public void builder(int maxLength) {
        Deque<Params> stack = new ArrayDeque<>();
        stack.addFirst(new Params("L", 1, 0));
        int step = 0;
        while (!stack.isEmpty()) {
            Params params = stack.getFirst();           
            if (params.budget() < 0 || params.word().length() > maxLength) {
                stack.removeFirst();
                step = params.nextStep();
            } else {
                if (step == 0) { 
                    System.out.println(params.word());
                    stack.addFirst(new Params(params.word() + "L", params.budget() + 1, 1));
                } else if (step == 1) {
                    stack.addFirst(new Params(params.word() + "R", params.budget - 1, 2));
                    step = 0;
                } else {
                    stack.removeFirst();
                    step = params.nextStep();
                }
            }
        }
    }

Hier ist step so etwas wie der "instruction pointer", nur eben abstrahiert zu Schritten, wobei step 0 bei Dir in Zeile 17 beginnt, step 1 in Zeile 22 und step 2 in Zeile 25 (Rücksprung aus der Methode). Im else-Zweig des äußeren if-Statements siehst Du also die drei Teile "L" hinzufügen, "R" hinzufügen und Methode beenden.

Die Zeilen 10 und 11 sowie 20 und 21 sind identisch - stellen eben ein return dar. Den step könnte man oben noch mit einbauen:

    public void builder(int maxLength) {
        Deque<Params> stack = new ArrayDeque<>();
        stack.addFirst(new Params("L", 1, 0));
        int step = 0;
        while (!stack.isEmpty()) {
            Params params = stack.getFirst();           
            if (step > 1 || params.budget() < 0 || params.word().length() > maxLength) {
                stack.removeFirst();
                step = params.nextStep();
            } else {
                if (step == 0) { 
                    System.out.println(params.word());
                    stack.addFirst(new Params(params.word() + "L", params.budget() + 1, 1));
                } else {
                    stack.addFirst(new Params(params.word() + "R", params.budget - 1, 2));
                    step = 0;
                }
            }
        }
    }