# Rekursion oder Iterative Lösung?



## districon (6. Mai 2021)

Hallo Menschen,
ich bin gerade nbei einer Aufgabe, bei der ich so gar nicht weiterkomme. Ich bräuchte einen kurzen Ansatz. Ich weiß nichtmal ob ich es mit Rekursion lösen soll oder iterativ. 

Erstellen Sie eine Klasse Brackets und implementieren Sie darin die öffentliche statische Methode bracket(BrExIt b, String s) die eine Zeichenkette s erhält und ein String-Array aller möglichen sinnvollen Klammerungen der Zeichen von s zurück gibt Bsp: ”ab” [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]
Ist s leer oder null, so muss auch das Ergebnis ein leeres Array sein. Die Reihenfolge der Elementein der Rückgabe ist irrelevant. Wichtig aber ist, dass kein Element in der Ergebnisliste mehrmals vorkommt und dass kein Klammerpaar leer bleibt oder ein anderes Klammerpaar direkt umschließt, also z.B. nicht„()“,nicht„((a))b“ und auch nicht „(((a)(b)))“. WICHTIG: Außer der Klasse String, dürfen Sie KEINE anderen Klassen oder Methoden aus der Java-API verwenden (auch NICHT System.out, HashSet oder Arrays.copyOf)! Verwenden Sie stattdessen unbedingt die über BrExIt bereitgestellte Methode.

Das ist die Methode:


```
public interface BrExIt {
    /**
     * Appends {@code result} to the end of {@code results}.
     *
     * @param results - array to which {@code result} should be appended to
     * @param result  - element to be appended to {@code results}
     * @return a new array containing all values from {@code results} (in original order) followed by {@code result} as last entry
     * @throws NullPointerException - if one or both arguments are {@code null}
     */
    String[] append(String[] results, String result);
}
```

Ich weiß überhaupt nicht wo ich hier anfangen soll. Kann mir vllt jmd helfen?
Danke!


----------



## Barista (6. Mai 2021)

Ich würde es rekursiv lösen.

Wenn die Methode einen Leerstring erhält, tut sie nichts (rRekursion terminiert).

Du schneidest das erste Zeichen per _substring(0 , 1)_ raus.

Dieses Zeichen verwendest Du jetzt gklammert und nicht geklammert.

Du rufst die Methode mit dem um das erste Zeichen gekürzten String auf.

Die Ergenisse (Array) verknüpfst Du mit geklammert und nicht geklammert.

Eventuell noch zusätzlich mit Klammer drum herum.

Dadurch entsteht das Ergebnis-Array für aufrufende Ebene.


----------



## districon (6. Mai 2021)

Barista hat gesagt.:


> Ich würde es rekursiv lösen.
> 
> Wenn die Methode einen Leerstring erhält, tut sie nichts (rRekursion terminiert).
> 
> ...


Ich darf aber keiner anderen Methoden verwenden und somit auch nicht substring()


----------



## fhoffmann (6. Mai 2021)

districon hat gesagt.:


> Ich darf aber keiner anderen Methoden verwenden und somit auch nicht substring()


Doch, die Methoden der Klasse String darfst du verwenden:


districon hat gesagt.:


> Außer der Klasse String, dürfen Sie KEINE anderen ...


----------



## districon (6. Mai 2021)

fhoffmann hat gesagt.:


> Doch, die Methoden der Klasse String darfst du verwenden:


Ah stimmt, übersehen


----------



## fhoffmann (6. Mai 2021)

Hast du denn die Idee von @Barista verstanden?

Du hast ja das Beispiel: Beim Verarbeiten von ”ab” erhälst du: [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]
Wenn du nun "xab" verarbeiten sollst, fragst du zunächst (rekursiv) ab, was die Verarbeitung von "ab" zurückliefert.
Dann gehst du das Array durch und machst aus jedem Element vier Elemente, beispielsweise für das erste ("ab"):
"xab", "(x)ab", "(xab)" und "((x)ab)".


----------



## districon (6. Mai 2021)

fhoffmann hat gesagt.:


> Hast du denn die Idee von @Barista verstanden?
> 
> Du hast ja das Beispiel: Beim Verarbeiten von ”ab” erhälst du: [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]
> Wenn du nun "xab" verarbeiten sollst, fragst du zunächst (rekursiv) ab, was die Verarbeitung von "ab" zurückliefert.
> ...


Ich habe zumindest den Ansatz verstanden, aber genauer muss ich selbst noch schauen


----------



## districon (6. Mai 2021)

fhoffmann hat gesagt.:


> Hast du denn die Idee von @Barista verstanden?
> 
> Du hast ja das Beispiel: Beim Verarbeiten von ”ab” erhälst du: [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]
> Wenn du nun "xab" verarbeiten sollst, fragst du zunächst (rekursiv) ab, was die Verarbeitung von "ab" zurückliefert.
> ...


Um ehrlich zu sein...eigentlich hab ichs noch nicht richtig verstanden xD


----------



## Barista (6. Mai 2021)

districon hat gesagt.:


> Um ehrlich zu sein...eigentlich hab ichs noch nicht richtig verstanden xD



Nimm mal den String _"abc"_ an.

"a" abschneiden.

Rekursiver Aufruf mit _"bc"_.

-> "b" abschneiden.

-> Rekursiver Aufruf mit "c",

-> -> "c" abschneiden.

-> -> -> RekursiverAufruf mit "" (Leerstring), Rekursion terminiert.

-> -> Rückgabe ["c", "(c)"]

-> "b" Kombinieren mit dem Ergebnis ["c", "(c)"]

-> Rückgabe ["bc", "b(c)", "(b)c", "(b)(c)"] (mit Klammer aussen drum herum dazu noch ["(bc)", "(b(c))", "((b)c)", "((b)(c))"])

"a" Kombinieren mit dem Ergebnis ["bc", "b(c)", "(b)c", "(b)(c)", "(bc)", "(b(c))", "((b)c)", "((b)(c))"]

["abc", "ab(c)", "a(b)c", "a(b)(c)", "a(bc)", "a(b(c))", "a((b)c)", "a((b)(c))", "(a)bc", "(a)b(c)", "(a)(b)c", "(a)(b)(c)", "(a)(bc)", "(a)(b(c))", "(a)((b)c)", "(a)((b)(c))"]

Dann noch mal alle mit Klammern aussen drum (kann Dein Code nun schon, wenn er es bei "b" schon gemacht hat).

Schreiben musst Du es schon selbst, sonst wäre es Betrug.


----------



## fhoffmann (6. Mai 2021)

Du musst in der Methode `bracket(BrExIt b, String s)` zunächst zwei Sonderfälle unterscheiden:
1. Der String s ist leer: Dann gibst du ein leeres Array zurück.
2. Der String s besteht nur aus einem Zeichen (z. B. "a"): Dann gibst du [a, (a)] zurück.
Ansonsten rufst du dich selbst für die zeichen ab dem zweiten Zeichen auf.
Aus jedem String im Ergebnis machst du vier Strings - wie oben beschrieben.


----------



## districon (6. Mai 2021)

fhoffmann hat gesagt.:


> Du musst in der Methode `bracket(BrExIt b, String s)` zunächst zwei Sonderfälle unterscheiden:
> 1. Der String s ist leer: Dann gibst du ein leeres Array zurück.
> 2. Der String s besteht nur aus einem Zeichen (z. B. "a"): Dann gibst du [a, (a)] zurück.
> Ansonsten rufst du dich selbst für die zeichen ab dem zweiten Zeichen auf.
> Aus jedem String im Ergebnis machst du vier Strings - wie oben beschrieben.




```
public class Brackets {
    public static String[] bracket(BrExIt b, String s) {
        String[] array = new String[] {};
        if (s == null || s == "") {
            return array;
        }
        if (s.length() == 1) {
            array[0] = s.substring(0,1);
            array[1] ="(" + s.substring(0,1) + ")";
        }
    }
}
```

So müsste es dann eigentlich schonmal richtig sein oder?


----------



## kneitzel (6. Mai 2021)

districon hat gesagt.:


> So müsste es dann eigentlich schonmal richtig sein oder?


Ich fürchte nicht ... im Text hat man Dir drei Unterscheidungen genannt:
a) String leer
b) String hat ein Zeichen
c) ansonsten ...

Das ist in deinem Code nicht zu erkennen.

Und dann natürlich ein paar Dinge in Deinem Code:
- Wie gross ist das Array array, dass Du da erzeugst?
- Wenn s genau ein Zeichen groß ist - was rufst Du da substring auf? Was meinst Du, dass Du da erreichen würdest?

Und generell: Dir ist bekannt, dass Du der Klasse z.B. noch eine main Methode geben kannst um deinen Code auch auszuprobieren? Ober der Code funktioniert oder nicht solltest Du also selbst testen können.


----------



## districon (6. Mai 2021)

kneitzel hat gesagt.:


> Ich fürchte nicht ... im Text hat man Dir drei Unterscheidungen genannt:
> a) String leer
> b) String hat ein Zeichen
> c) ansonsten ...
> ...


Das Array ist ja noch nicht initialisiert


----------



## districon (6. Mai 2021)

```
public class Brackets {
    public static String[] bracket(BrExIt b, String s) {
        String[] array = new String[] {};
        if (s == null || s == "") {
            return array;
        }
        if (s.length() == 1) {
            array[0] = s;
            array[1] ="(" + s + ")";
            return array;
        }
        else {
            int a = 0;
            return bracket(b, s.substring(a + 1, s.length()-1));
        }
    }

}
```

Jetzt muss ich nur noch alles in ein Array packen


----------



## fhoffmann (6. Mai 2021)

districon hat gesagt.:


> array[0] = s;


Das wird zu IndexOutOfBoundsException führen.
Du musst stattdessen aufrufen:

```
array = b.append(array, s);
```


----------



## kneitzel (6. Mai 2021)

districon hat gesagt.:


> Das Array ist ja noch nicht initialisiert


Wenn man diesen Code betrachtet:

```
String[] array = new String[] {};
```
dann ist das auch eine Initialisierung. Es wird ja ein neues Array der Länge 0 erzeugt und zugewiesen.

Dann ist der Hinweis von @fhoffmann für das zweite if wichtig.

Den else Zweig solltest Du dir aber auch noch einmal ansehen. Was soll denn da raus kommen?
Nehmen wir den Fall "ab" - das soll dann nur der rekursive Aufruf sein, also "b", "(b)"? Oder willst Du mit dem Ergebnis des Rekursiven Aufrufes noch irgend etwas machen?


----------



## districon (6. Mai 2021)

kneitzel hat gesagt.:


> Wenn man diesen Code betrachtet:
> 
> ```
> String[] array = new String[] {};
> ...


Die Werte muss ich noch ins Array stecken


----------



## districon (6. Mai 2021)

und den normalen String muss ich auch noch ins Array tun


----------



## Barista (6. Mai 2021)

districon hat gesagt.:


> Verwenden Sie stattdessen unbedingt die über BrExIt bereitgestellte Methode.
> 
> Das ist die Methode:
> 
> ...


Mir ist noch eingefallen, dass diese Methode in dem Interface mit dem EU-Austritts-Namen wahrscheinlich die eigentliche rekursive Methode sein soll.

Nun ja, hier fehlt der Anfangsaufruf, aber es soll wahrscheinlich nicht so einfach sein.

Anfangsaufruf entsprechend meinem Beispiel mit String "abc":

[CODE lang="java" title="Anfangsaufruf der Methode BrExIt.append"]BrExItImpl generator = new BrExItImpl(); // eine Klasse, die das vorgegebene Interface implementiert

String[] result = generator.append(new String[0], "abc");[/CODE]
Die Implementierung der Methode _append_ ruft sich selbst wieder rekursiv auf (Könnte sein).


----------



## districon (6. Mai 2021)

Barista hat gesagt.:


> Mir ist noch eingefallen, dass diese Methode mit dem EU-Austritts-Namen wahrscheinlich die eigentliche rekursive Methode sein soll.
> 
> Nun ja, hier fehlt der Anfangsaufruf, aber es soll wahrscheinlich nicht so einfach sein.
> 
> ...


Ich glaube eher nicht. Wir haben noch gar keine Interfaces bzw. Klassen durchgemacht


----------



## kneitzel (6. Mai 2021)

Barista hat gesagt.:


> Mir ist noch eingefallen, dass diese Methode in dem Interface mit dem EU-Austritts-Namen wahrscheinlich die eigentliche rekursive Methode sein soll.


Unwahrscheinlich. Das wird eher etwas sein, das den Schülern das Hinzufügen von Werten zu einem Array abnehmen soll. Dynamische Listen dürften halt noch fehlen ....

Rekursion kann ja - so wie in #10 von @fhoffmann ausgeführt - so durchaus Sinn machen. Und die Aufrufe, die dann mit dem Parameter notwendig sind, hat @fhoffmann in #15 kurz aufgezeigt.


----------



## districon (7. Mai 2021)

fhoffmann hat gesagt.:


> Du musst in der Methode `bracket(BrExIt b, String s)` zunächst zwei Sonderfälle unterscheiden:
> 1. Der String s ist leer: Dann gibst du ein leeres Array zurück.
> 2. Der String s besteht nur aus einem Zeichen (z. B. "a"): Dann gibst du [a, (a)] zurück.
> Ansonsten rufst du dich selbst für die zeichen ab dem zweiten Zeichen auf.
> Aus jedem String im Ergebnis machst du vier Strings - wie oben beschrieben.


Hey, also ich muss jetzt glaube ich noch 3 Dinge tun. 
1. Den normalen String auch noch ins Array tun (Bei ab ist auch auch einfach nur ab ohne Klammern dabei)
2. Die Einträge irgendwie verknüpfen, also dass er  "a" mit dem Ergebnis ["b", "(b)"] kombiniert
3. Die Fälle ausschließen, womit andere Klammernpaare direkt umschließt werden.
Sehe ich das richtig so?


----------



## Barista (7. Mai 2021)

Mich interessiert mal der Kontext:

Ist dies eine Aufgabe für jemanden, bei dem man erwartet, dass er/sie im Berufsleben programmieren muss (Fachinformatiker, Informatik-Studium oder so)

oder ist dies eine Aufgabe im allgemeinen Informatik-Unterricht?

Für allgemeinen Informatik-Unterricht finde ich die Aufgabe zu schwer.


----------



## districon (7. Mai 2021)

Barista hat gesagt.:


> Mich interessiert mal der Kontext:
> 
> Ist dies eine Aufgabe für jemanden, bei dem man erwartet, dass er/sie im Berufsleben programmieren muss (Fachinformatiker, Informatik-Studium oder so)
> 
> ...


technisches Studium mit vielen Informatikinhalten. 2. Semester


----------



## Barista (7. Mai 2021)

districon hat gesagt.:


> 1. Den normalen String auch noch ins Array tun (Bei ab ist auch auch einfach nur ab ohne Klammern dabei)


Nach meinem Algorithmus-Vorschlag nicht.



districon hat gesagt.:


> Die Einträge irgendwie verknüpfen, also dass er "a" mit dem Ergebnis ["b", "(b)"] kombiniert


Ja, geht bei Java-Strings mit dem + - Operator.



districon hat gesagt.:


> Die Fälle ausschließen, womit andere Klammernpaare direkt umschließt werden.


Nach meinem Algorithmus-Vorschlag nicht.


districon hat gesagt.:


> Sehe ich das richtig so?


Leg einfach mal los, schwimmen lernt man nur im Wasser.


----------



## Barista (7. Mai 2021)

districon hat gesagt.:


> technisches Studium mit vielen Informatikinhalten. 2. Semester


Dann musst da wohl durch.


----------



## districon (7. Mai 2021)

Barista hat gesagt.:


> Dann musst da wohl durch.


Ja. Es ist nur die erste Rekursionsaufgabe und das verstehe ich noch nicht so gut


----------



## districon (7. Mai 2021)

Barista hat gesagt.:


> Dann musst da wohl durch.


Ich versuche wirklich die ganze Zeit aber ich schaff überhaupt nichts außer das hier:#

```
public class Brackets {
    public static String[] bracket(BrExIt b, String s) {
        String[] array = new String[] {};
        if (s == null || s == "") {
            return array;
        }
        if (s.length() == 1) {
            array = b.append(array, s);
            array = b.append(array, "(" + s + ")");
            return array;
        }
        else {
            int a = 0;
            return bracket(b, s.substring(a + 1, s.length()-1));
            array = b.append(array, )
        }
    }

}
```


----------



## kneitzel (7. Mai 2021)

Dann schau Dir nur einmal den else zweig an:

Das Ergebnis des Rekursiven Aufrufs ist noch nicht das Endergebnis. Daher kannst Du nicht mit return das Ergebnis als Endergebnis zurück geben.

Du willst also das Ergebnis irgendwo speichern um dann damit noch irgendwas im Anschluss machen zu können.


----------



## Barista (7. Mai 2021)

Für die Rekursion benötigst Du eine zweite Methode, die sich selbst immer wieder aufruft.

[CODE lang="java" title="rekursive Methode"]

public static String[] bracket(BrExIt b, String s) {
    return bracketRecursive(s, b);
}

private static String[] bracketRecursive( String s , BrExIt b ) { // Du kannst die Parameter auch tauschen

    if ( s == null || s.empty() ) {
        return ??? // hier solltest Du schon mal probieren, was funktioniert
    }

    final String head = s.substring( 0 , 1 );

    final String tail = s.substring( 1 );

    final String[] recursiveCallResult = bracketRecursive(tail, b);

    ??? Zusammenfügen ???

    return ??? Deine Aufgabe ???;
}[/CODE]


----------



## districon (7. Mai 2021)

Also muss es im Rekursionsfall irgendwie sowas sein:


Barista hat gesagt.:


> Für die Rekursion benötigst Du eine zweite Methode, die sich selbst immer wieder aufruft.
> 
> [CODE lang="java" title="rekursive Methode"]
> 
> ...


In Zeile 8 muss ich doch einfach ein leeres Array zurückgeben


----------



## fhoffmann (7. Mai 2021)

districon hat gesagt.:


> return bracket(b, s.substring(a + 1, s.length()-1));


Stattdessen musst du etwas schreiben wie

```
String[] zwischenergebnis = bracket(b, s.substring(1));
```
Und dann über das Array "zwischenergebnis" iterieren (in einer for-Schleife) und aus jedem String aus dem Zwischenergebnis vier Strings machen.


----------



## districon (7. Mai 2021)

fhoffmann hat gesagt.:


> Stattdessen musst du etwas schreiben wie
> 
> ```
> String[] zwischenergebnis = bracket(b, s.substring(1));
> ...


Ah hab mir gerade nochmal substring angeschaut...jetzt versteh ich es ein wenig besser


----------



## Barista (7. Mai 2021)

Dein Problem ist, dass Rekursion bereits ein schwierigeres Problem als eine einfache iterative Aufgabe, wie das Zeichnen eines Ascii-Weihnachtsbaumes in der Konsole ist.

Dies solltest Du erst mal versuchen bzw. müsstest Du bereits können.

Wenn Du Dir nicht vorher bereits das algorithmische Denken angewöhnt hast
(Wie schreibe ich ein Programm, welches XYZ macht?),
bist Du mit dem Problem auf höherer Ebene aufgeschmissen.

Und vor allem, Du musst es von selbst wollen (ist zumindest meine Meinung).

Man wird nicht zum Programmierer, weil man eine Schulung gemacht hat, sondern weil man sich freiwillig und gern mit Algorithmen beschäftigt.

Ich habe Rekursion erst nach einem Jahr oder wahrscheinlich noch mehr Programmier-Praxis verwendet.


----------



## districon (7. Mai 2021)

districon hat gesagt.:


> Ah hab mir gerade nochmal substring angeschaut...jetzt versteh ich es ein wenig besser


Also kann zwischenergenbnis sowas sein wie [(b), b, (a), a] ? Und ich muss es jetzt nur noch kombinieren?


----------



## districon (7. Mai 2021)

Barista hat gesagt.:


> Dein Problem ist, dass Rekursion bereits ein schwierigeres Problem als einfache iterative Aufgabe, wie das Zeichnen eines Ascii-Weihnachtsbaumes in der Konsole ist.
> 
> Dies solltest Du erst mal versuchen bzw. müsstest Du bereits können.
> 
> ...


Ja, wie gesagt das ist die erste Aufgabe mit Rekursion. Davor hat es eigentlich immer ganz gut geklappt. Ich mach das eigentlich auch gerne, nur bei solchen Aufgaben zweifle ich halt immer daran ob ich das überhaupt kann.


----------



## Barista (7. Mai 2021)

districon hat gesagt.:


> In Zeile 8 muss ich doch einfach ein leeres Array zurückgeben


Probier es aus.


----------



## districon (7. Mai 2021)

Barista hat gesagt.:


> Probier es aus.


Ich werde mir erst nochmal ein paar Videos zu Rekursion anschauen


----------



## Barista (7. Mai 2021)

districon hat gesagt.:


> Also kann zwischenergenbnis sowas sein wie [(b), b, (a), a] ? Und ich muss es jetzt nur noch kombinieren?


a +alle+ [(b), b] => [a(b), ab]

[(a), a] +alle+ [(b), b] => [(a)(b), (a)b, a(b), ab] (kartesisches Produkt)

In diesem Fall soll '+alle+' so etwas wie Operator kartesisches Produkt bedeuten


----------



## districon (7. Mai 2021)

Können wir kurz nochmal meinen Code betrachten?

```
public class Brackets {
    public static String[] bracket(BrExIt b, String s) {
        String[] array = new String[] {};
        if (s == null || s == "") {
            return array;
        }
        if (s.length() == 1) {
            array = b.append(array, s);
            array = b.append(array, "(" + s + ")");
            return array;
        }
        else {
            String[] zwischenergebnis = bracket(b, s.substring(1));
            
        }
    }

}
```
 Wenn ich als Eingabe beispielsweise "ab" habe. Das geht dann bis zum else-Fall und das a wird abgeschnitte. Da s jetzt gleich 1 ist geht es in die if Bedingung und im array steht dann ["b", "(b)"]. Jetzt bin ich mir nicht mehr sicher wie es weitergeht. Wird das Araay dann im nächsten Schritt zu ["b", "(b)", "a", "(a)"] oder wie geht es da weiter?


----------



## kneitzel (7. Mai 2021)

Was in dem Fall raus kommen soll, hast Du doch schon in dem ersten Post als Beispiel genannt:


> Bsp: ”ab” [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]


----------



## districon (7. Mai 2021)

kneitzel hat gesagt.:


> Was in dem Fall raus kommen soll, hast Du doch schon in dem ersten Post als Beispiel genannt:


Ja was rauskommen sollte. Aber ich meinte damit was speziell bei meinem Code da rauskommt


----------



## kneitzel (7. Mai 2021)

Dann schau Dir doch einfach erst einmal die beiden Mengen an und schau, was Du da evtl. an Regeln festlegen kannst ....

Also Du hast den abgespalteten Buchstaben "a" und dann die Menge { "b", "(b)" }

Was kannst Du denn alles bauen? Also was man z.B. sehen sollte:
Vor jedes Element kommt mal a und mal (a), d.h. Du hast dann schon einmal
"ab", "a(b)", "(a)b", "(a)(b)"
Mit der Regel haben wir aber noch nicht alles ... denn es fehlen noch ein paar Ergebnisse. Welche Ergebnisse fehlen? Erkennst Du noch eine weitere Regel?


----------



## districon (7. Mai 2021)

kneitzel hat gesagt.:


> Dann schau Dir doch einfach erst einmal die beiden Mengen an und schau, was Du da evtl. an Regeln festlegen kannst ....
> 
> Also Du hast den abgespalteten Buchstaben "a" und dann die Menge { "b", "(b)" }
> 
> ...


(ab), ((a)b), (a(b)) fehlen noch. Bei manchen muss noch eine Klammer rum


----------



## kneitzel (7. Mai 2021)

districon hat gesagt.:


> (ab), ((a)b), (a(b)) fehlen noch. Bei manchen muss noch eine Klammer rum


Bei sowas musst Du exakt arbeiten!
a) Prüf, ob das wirklich stimmt mit den drei Elementen. (Vermutlich nicht, sonst würde ich das so nicht nennen)
b) Generell immer schauen, was für Regeln du findest. "bei manchen" ist keine Aussage, die weiter hilft. Du musst klare Regeln erkennen und dann umsetzen bei sowas.


----------



## districon (7. Mai 2021)

kneitzel hat gesagt.:


> Bei sowas musst Du exakt arbeiten!
> a) Prüf, ob das wirklich stimmt mit den drei Elementen. (Vermutlich nicht, sonst würde ich das so nicht nennen)
> b) Generell immer schauen, was für Regeln du findest. "bei manchen" ist keine Aussage, die weiter hilft. Du musst klare Regeln erkennen und dann umsetzen bei sowas.


Es werden noch ein zusätzliche Strings hinzugefügt. Bei allen wird nochmal eine Klammer ergänzt außer bei (ab).


----------



## kneitzel (7. Mai 2021)

districon hat gesagt.:


> Es werden noch ein zusätzliche Strings hinzugefügt. Bei allen wird nochmal eine Klammer ergänzt außer bei (ab).


Nein, ich weiss nicht, was Du machst, aber Du solltest das GENAU aufschreiben. Wenn Du so oberflächig an die Aufgabe heran gehst, dann kann es nichts werden! Das ist jetzt kein Problem der Software-Entwicklung sondern es geht einfach nur darum, eine Problematik zu verstehen. Ehe man irgend etwas in ein Programm schreiben kann, musst Du die Problematik verstanden haben.

Das ist doch schon die Voraussetzung, damit Du auch Deinen Code testen kannst.

Und das jetzt erschreckt mich etwas muss ich gestehen. Denn jetzt musst Du nur hin gehen und zählen:
Wie viele Elemente sind in der Lösung:  [ab, (a)b, ((a)(b)), a(b), (ab), (a)(b), ((a)b), (a(b))]?
Wie viele Elemente sind in der ersten Teillösung: "ab", "a(b)", "(a)b", "(a)(b)"?
Wie viele Elemente fehlen dann noch?
Wie viele Elemente sind in Deiner Aussage, was noch fehlt: (ab), ((a)b), (a(b))?

Dann einfach die Aussage von Dir: "Bei allen wird nochmal eine Klammer ergänzt außer bei (ab)": is denn (ab) Bestandteil der ersten Teillösung?

Wenn Du das alles richtig betrachtest, dann hast Du sofort die Lösung, denn dann findest Du, dass ((a)(b)) ebenfalls fehlt. Und dann findest Du, dass alle Elemente der Teillösung noch einmal geklammert dazu kommen.

Das ist halt ähnlich wie bei einem Zeichen: b und (b) ist da die Lösung. nur eben ist b jetzt ein Array mit Teillösungen und die kommen mit und ohne Klammern in die Lösung.

Vielleicht hakt es auch noch an dem generellen Verständnis. Eine etwas einfachere Sache ist alle binären Zahlen mit x Stellen zu bauen.
0 Stellen: {}
1 Stelle: [ 0, 1 ]
x Stellen hatte alle Elemente aus x-1 - einmal mit 0 davor und einmal mit 1 davor.

Hier ist es etwas komplexer, denn wir haben mehrere Möglichkeiten als nur 0/1 und diese sind nicht ganz so übersichtlich, weil das halt durch diverse Klammerungen dargestellt wurde. Aber das Prinzip ist genau das Gleiche.


----------



## districon (7. Mai 2021)

kneitzel hat gesagt.:


> Nein, ich weiss nicht, was Du machst, aber Du solltest das GENAU aufschreiben. Wenn Du so oberflächig an die Aufgabe heran gehst, dann kann es nichts werden! Das ist jetzt kein Problem der Software-Entwicklung sondern es geht einfach nur darum, eine Problematik zu verstehen. Ehe man irgend etwas in ein Programm schreiben kann, musst Du die Problematik verstanden haben.
> 
> Das ist doch schon die Voraussetzung, damit Du auch Deinen Code testen kannst.
> 
> ...


Danke! Jetzt habe ich verstanden warum das Problem rekursiv ist


----------



## districon (7. Mai 2021)

kneitzel hat gesagt.:


> Nein, ich weiss nicht, was Du machst, aber Du solltest das GENAU aufschreiben. Wenn Du so oberflächig an die Aufgabe heran gehst, dann kann es nichts werden! Das ist jetzt kein Problem der Software-Entwicklung sondern es geht einfach nur darum, eine Problematik zu verstehen. Ehe man irgend etwas in ein Programm schreiben kann, musst Du die Problematik verstanden haben.
> 
> Das ist doch schon die Voraussetzung, damit Du auch Deinen Code testen kannst.
> 
> ...




```
public class Brackets {
    public static String[] bracket(BrExIt b, String s) {
        String[] array = new String[] {};
        if (s == null || s == "") {
            return array;
            
        }
        if (s.length() == 1) {
            array = b.append(array, s);
            array = b.append(array, "(" + s + ")");
            return array; //for Schleife für erste Teillösung
        }
        else {
            String[] zwischenergebnis = bracket(b, s.substring(1));
            //return Anweisung
        }
    }

}
```

Dann müsste es im Prinzip so sein


----------



## kneitzel (7. Mai 2021)

Das freut mich. Sorry, wenn wir da das Verständnisproblem nicht schneller erkannt haben. Dadurch sind ggf. Erläuterungen auch einfach noch nicht fruchten können... 



districon hat gesagt.:


> Dann müsste es im Prinzip so sein


Damit hast Du dann das Zwischenergebnis.
Aus jedem Element des Zwischenergebnisses musst du nun die 8 neuen Elemente hinzufügen.


----------



## Barista (7. Mai 2021)

In meiner letzten Firma mussten Bewerber eine Aufgabe dieses Schwierigkeitsgrades innerhalb eines Vorstellungsgesprächs lösen.


----------



## fhoffmann (7. Mai 2021)

kneitzel hat gesagt.:


> Aus jedem Element des Zwischenergebnisses musst du nun die 8 neuen Elemente hinzufügen


Das ist falsch, aus jedem Element müssen nur vier neue Elemente gemacht werden; die Klammerung um "b" existiert ja schon.


----------



## kneitzel (8. Mai 2021)

fhoffmann hat gesagt.:


> Das ist falsch, aus jedem Element müssen nur vier neue Elemente gemacht werden; die Klammerung um "b" existiert ja schon.


Ja, das ist natürlich richtig, danke für die Verbesserung. Falls die Erläuterung von @fhoffmann noch nicht ausreichend war:
Wir haben zwei Schritte: ersten Buchstaben mit und ohne Klammern
und dann die entstandendenen Ergebnisse mit und ohne Klammern.
==> Zwei Verdoppelungen, d.h. 4 Elemente.

Jetzt sollten wir aber diese gefundene (vermeintliche) Lösung noch etwas verifizieren. Wir haben die Idee von @fhoffmann aus #6 umgesetzt, aber die Idee wurde bisher noch nicht verifiziert. Das hätte man schon an seinem Beispiel machen können/sollen aber das wurde irgendwie versäumt.

Er hat das Beispiel xab gebracht und da gibt es nur die Ergebnisse von ab für die jeweils die Elemente:
xt
(x)t
(xt)
((x)t)
für alle t Element aus der Menge aller Lösungen aus dem Aufruf aus "ab". 

Was dabei auffallen sollte ist nun, dass z.B. "(xa)b" eine gültige Klammerung ist, aber diese in der Lösungsmenge nicht auftaucht.

Somit ist die bisherige Lösung noch nicht korrekt und somit zu erweitern. Wenn ich also 3 Zeichen habe, muss ich nicht nur das erste Zeichen mal abtrennen sondern auch mal 2 Zeichen. Bei n Zeichen habe ich dann einfach eine Schleife, die dann alles in alle möglichen zwei Teile trennen könnte.

Und dann ist da noch das wichtige Thema:


districon hat gesagt.:


> Wichtig aber ist, dass kein Element in der Ergebnisliste mehrmals vorkommt


Ohne Grund wird da ja das HashSet nicht explizit erwähnt worden sein 



Barista hat gesagt.:


> In meiner letzten Firma mussten Bewerber eine Aufgabe dieses Schwierigkeitsgrades innerhalb eines Vorstellungsgesprächs lösen.


Aber das ist keine Aufgabe für einen Junior würde ich sagen. Das ist eine Aufgabe, die bei den Codility-Tests, auf die wir z.B. zugreifen, als schwere Aufgabe geführt werden dürfte.


----------



## fhoffmann (8. Mai 2021)

kneitzel hat gesagt.:


> Was dabei auffallen sollte ist nun, dass z.B. "(xa)b" eine gültige Klammerung ist, aber diese in der Lösungsmenge nicht auftaucht.


Oh Gott, das habe ich nicht gesehen - nun wird es ja richtig komplizert.
Dann ist ja auch "(x(ab))c" oder "(x(a)b)c" nicht in der Lösungsmenge enthalten.


----------



## kneitzel (8. Mai 2021)

fhoffmann hat gesagt.:


> Oh Gott, das habe ich nicht gesehen - nun wird es ja richtig komplizert.
> Dann ist ja auch "(x(ab))c" oder "(x(a)b)c" nicht in der Lösungsmenge enthalten.


Ja genau, ich selbst sehe daher als rekursiven Algorithmus derzeit, dass man eine Schleife hat in der man dann alle Möglichkeiten aufruft, mit denen man es in zwei Teile teilen kann.
- Also wenn ich abcd habe, dann rufe ich rekursiv auf für a + bcd, ab  + cd und abc + d und erhalte so jedes Mal zwei Array (Mengen) zurück. (Die weiteren Unterteilungen kommen dann ja automatisch).
- Bei den Ergebnissen, die man erhält, erstellt man dann sozusagen das "Kreuzprodukt" und fügt jedes Ergebnis dann hinzu (2 Mal, geklammert und nicht geklammert)
- Beim hinzufügen wird aber erst geprüft, ob das hinzuzufügende Element bereits vorhanden ist. Ist dies der Fall, wird nicht eingefügt.

Das wäre meine erste Implementation um dann die Ergebnisse zu betrachten.... Wenn man sich anschaut, was alles doppelt gemacht wird, dann findet sich hoffentlich noch die eine oder andere Optimierung. Aber das exponentielle Laufzeitverhalten hat man auf jeden Fall


----------



## fhoffmann (8. Mai 2021)

kneitzel hat gesagt.:


> Wenn man sich anschaut, was alles doppelt gemacht wird, dann findet sich hoffentlich noch die eine oder andere Optimierung.


Es wäre auch mein Ehrgeiz, doppelte Elemente durch die Programmierung zu verhindern (und diesen Job nicht einer Menge (java.util.Set) zu überlassen).


----------

