Liste aller Kombintionen mit Einschränkungen

berndoa

Top Contributor
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.


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

Top Contributor
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

Top Contributor
Hier schonmal ein Denkanstoß für eine rekursive Lösung:
Java:
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

Bekanntes Mitglied
Iterativ läßt sich das sicher auch umsetzen, wird aber weit weniger elegant aussehen. Eine rekusive Variante findest Du hier.
Java:
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

Top Contributor
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

Top Contributor
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

Super-Moderator
Mitarbeiter
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

Top Contributor
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.)

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

Top Contributor
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.

Java:
    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:
Java:
    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;
                }
            }
        }
    }
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Liste aller Com-Ports - zweistellige Ports? Allgemeine Java-Themen 15
S AWT Wie bekomme ich eine Liste aller chars in einem Font? Allgemeine Java-Themen 3
K Liste aller implementierenden Klassen einer Oberklasse anzeigen Allgemeine Java-Themen 4
I Liste aller bekannten Packages Allgemeine Java-Themen 6
TheSepp Wie kann man Leerzeichen aus einer Array liste entfernen? Allgemeine Java-Themen 10
B Liste ändern während Iteration über Diese? Allgemeine Java-Themen 16
D Erste Schritte Liste erweitern Allgemeine Java-Themen 11
sserio Variablen Liste erstellt und ein Problem mit dem Index Allgemeine Java-Themen 6
L allgemein Strings händisch in Liste sortieren Allgemeine Java-Themen 47
M einfach verkettete Liste verstehen Allgemeine Java-Themen 23
Drachenbauer wie kann ich alle instanzen einer Klasse durchsehen, ohne, dass diese in einer Liste erzeugt wurden? Allgemeine Java-Themen 11
Gaudimagspam Skip Liste erstellen in Java Allgemeine Java-Themen 3
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
bueseb84 Spring Boot Entity mit Liste Allgemeine Java-Themen 4
MiMa Werte in liste speichern? Allgemeine Java-Themen 3
Curtis_MC Collections Liste anhand mehrere Kriterien sortieren Allgemeine Java-Themen 6
K verkettete Liste Allgemeine Java-Themen 3
G Liste (UsageStats) sortieren (Android) Allgemeine Java-Themen 5
T Google Links in einer Liste Allgemeine Java-Themen 4
looparda Liste filtern nach Prädikaten verschiedener Typen Allgemeine Java-Themen 3
OSchriever Einfach verkettete Liste ändern Allgemeine Java-Themen 43
L Liste überschreibt alte Elemte Allgemeine Java-Themen 10
H Länge einer verketteten Liste Allgemeine Java-Themen 4
E Erstellen einer Liste mit einer maximalen Menge an Elementen Allgemeine Java-Themen 13
P Element einer Liste wurde hinzugefügt, aber es gibt keinen Zugriff Allgemeine Java-Themen 2
S Methoden Liste soll Methode aus innerer Klasse aufrufen Allgemeine Java-Themen 4
L Erste Schritte Liste von Datums filter nach Monate Allgemeine Java-Themen 4
Y Liste in Stream Packen Allgemeine Java-Themen 1
K Einfache Verkettete Liste mit Node Allgemeine Java-Themen 3
perlenfischer1984 Reflection : Element in generische Liste hinzufügen Allgemeine Java-Themen 4
perlenfischer1984 Liste mit generics zurück liefern Allgemeine Java-Themen 8
S Verkettete (Teil)Liste sortieren ( rekursiv bis n) Allgemeine Java-Themen 2
G Liste zwischen zwei Kalenderdaten erstellen Allgemeine Java-Themen 3
B Wie vergleiche ich Strings in einer Liste? Allgemeine Java-Themen 5
Viktim Threads Liste In unterschiedlichen Threads bearbeiten Allgemeine Java-Themen 23
A Collections Inhalt einer Liste mit Inhalt anderer Liste vergleichen ? Allgemeine Java-Themen 7
I Abstrakte Datentypen - Liste Allgemeine Java-Themen 9
D Datentypen Klassenattribut aus Objekt in generischer Liste Allgemeine Java-Themen 15
P Liste zu Objekt umwandeln Allgemeine Java-Themen 4
Z In die Liste kann ich nichts adden Allgemeine Java-Themen 16
C Liste checken auf MINDESTENS ein Objekt | Bukkit Allgemeine Java-Themen 3
M liste von listen anders ausgeben Allgemeine Java-Themen 1
B Per Buttonklicks einer Liste Wörter hinzufügen - Wie umsetzen? Allgemeine Java-Themen 11
H Liste sortieren anhand optionalem Property Allgemeine Java-Themen 3
L Liste führt sich nicht weiter Allgemeine Java-Themen 5
A Input/Output Liste der Dateien in einem Ordner in einer Jar Datei erhalten Allgemeine Java-Themen 11
J Fragen zu generischer doppelt verketteter Liste (bei fehlendem Grundverständnis) Allgemeine Java-Themen 1
B Prüfen, ob ein Element in der Liste nicht existiert Allgemeine Java-Themen 3
B Klassen JTable mit einer Liste Allgemeine Java-Themen 0
X HTTP Auslesen der Ergebnisse von einer Webseite und in eine Liste packen Allgemeine Java-Themen 1
A Auslesen einer Datei sowie ausgeben als Liste in App Allgemeine Java-Themen 5
E Liste löscht sich selbstständig Allgemeine Java-Themen 5
H Liste von Objekten generisch sortieren Allgemeine Java-Themen 0
D Liste anhand Standardnormalverteilung befüllen Allgemeine Java-Themen 1
M Threads synchroner Zugriff (add/delete/read) auf eine Liste Allgemeine Java-Themen 6
T Datentypen Eine Liste - verschiedenen Klassen - eine Abstracte Klasse Allgemeine Java-Themen 3
M Werte aus DB in Liste speichern ohne mehrfach speicherung Allgemeine Java-Themen 18
G Liste anzahl der gleichen Objekte Allgemeine Java-Themen 6
S Pattern.Match Suche: For Schleife einbinden und in Liste schreiben Allgemeine Java-Themen 3
O aus Liste ein beliebiges Element auswählen Allgemeine Java-Themen 7
O MVC - wo Liste der ComboBox-Items ermitteln Allgemeine Java-Themen 3
MiMa Liste von Pfaden in eine textArea schreiben Allgemeine Java-Themen 7
K kontinuierlich aktuelle Bestellsystem-Liste mit farbigem Status Allgemeine Java-Themen 2
A Auswählbare Liste Allgemeine Java-Themen 2
D Sortieren von Liste zu unperformant Allgemeine Java-Themen 6
N Liste gesucht Allgemeine Java-Themen 2
Z Sortiertes Einfügen in doppelt verkettete Liste Allgemeine Java-Themen 5
S Probleme beim Auslesen einer Liste Allgemeine Java-Themen 8
O JSON String bauen aus Liste Allgemeine Java-Themen 2
M Über Liste verschiendene JComponents mit eigenem implementierten Interface ansprechen Allgemeine Java-Themen 7
T Hashmap mit geordneter/ungeordneter liste als Value Allgemeine Java-Themen 5
D Zugriff auf Array-Liste Allgemeine Java-Themen 19
S Threads Liste mit Objekten in Teillisten zerlegen und abarbeiten Allgemeine Java-Themen 3
R ThreadPool - vorhandene thread liste überprüfen bzw. aufräumen Allgemeine Java-Themen 3
pg1337 Liste füllen Allgemeine Java-Themen 2
U Große Liste von Strings mit indiziertem Zugriff Allgemeine Java-Themen 31
B Properties File Liste Allgemeine Java-Themen 3
Gossi Collections Liste zusammenfassen für JSP Allgemeine Java-Themen 4
Gossi Collections (Unbekannte) Liste Sortieren Allgemeine Java-Themen 10
T Collections Liste schnell/nebenläufig durchgehen Allgemeine Java-Themen 2
M Objekt aus Liste in Liste suchen/löschen Allgemeine Java-Themen 6
Q "Doppelte" Einträge einer Liste entfernen Allgemeine Java-Themen 14
C Exponentielle Verteilung in einer Liste Allgemeine Java-Themen 7
Nic.o liste der installierten Zertifikate ?! Allgemeine Java-Themen 3
T Liste mit GregorianCalendar-Objekten in List einlesen, mit Collection sortieren und ausgeben Allgemeine Java-Themen 3
M Verständnisfragen bezüglich Liste Allgemeine Java-Themen 3
J Zeichenketten-Liste filtern Allgemeine Java-Themen 6
S Aus einer Liste<Oberklasse> alle Elemente die eine bestimmte Unterklasse von Oberklasse haben filter Allgemeine Java-Themen 8
M Eintrag verschwindet aus Liste Allgemeine Java-Themen 3
E Objekte in einer Liste suchen. Allgemeine Java-Themen 4
I Über eine Liste iterieren und Objekte löschen. Wie löst man das sauber? Allgemeine Java-Themen 5
reibi Kopie einer Liste Allgemeine Java-Themen 4
N Liste mit Map abgleichen extrem langsam Allgemeine Java-Themen 6
C Darstellung der Liste bei vielen Daten extrem langsam Allgemeine Java-Themen 11
T Liste sortieren Allgemeine Java-Themen 6
L Objekte in Liste packen Allgemeine Java-Themen 2
N Liste aendern waehrend des iterierens ueber selbige Allgemeine Java-Themen 11
B Datenstruktur: Liste Allgemeine Java-Themen 5
S Liste mit verschiedenden Objekten Allgemeine Java-Themen 15
D Einfach verkettete Liste Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben