Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 11.5: Klammern
Hallo,
wäre es möglich zu erfahren wie viele mögliche Klammerungen ein String hat, wenn dieser Länge 3 bzw. 4 hat? Ist beim Testen etwas mühsam durchzusehen, ob man alle Möglichkeiten getroffen hat…Wenn man zumindest die Anzahl der Möglichkeiten mal vergleichen könnte, wäre das schonmal hilfreich =)
Geht in etwa in die Richtung der Catalan-Zahlen - aber die Aufgabe erlaubt/verlangt mehr als „nur“ diese Anzahl… 
Das Ausrechnen im Voraus ist „hier nicht angezeigt“… :-p duckundweg
Für euren Test, hier die genauen Anzahlen an Klammerungen: http://oeis.org/A054726.
Hier sind Super-Catalan-Zahlen “angezeigt”: 2^n* (http://oeis.org/A001003)(n-2)
Super, vielen Dank. Das hat mir jetzt doch einiges an Zeit erspart 
Ich hänge bei der Aufgabe irgendwie. Ich habe alle möglichen Versuche unternommen, Rekursion und Listenabstraktion ineinander zu schachteln, aber mir fehlen entweder die gesamten Ausdrücke in Klammern oder ich zerteile den String falsch, so dass ich dann, wenn ich es mit 3 Buchstaben probiere gerne auch “abbc” etc. mit drin habe…
Es wurden in der Aufgabenstellung ja schon viele Hinweise gegeben, welche Funktionen man benutzen kann, aber zusammen bekomme ich diese einzelnen Hinweise nicht. Gibt es noch einen Tipp, den man gefahrlos geben kann ohne was zu verraten? Muss ich z.B. map, currying oder irgendsowas benutzen? Die Lösung müsste doch wahrscheinlich ohne Hilfsfunktionen gehen?
Ja gleiches Problem bei mir. Tu mich auch schwer wirklich nen vernünftigen Weg zu finden…erstens die Rekursion richtig hinzubekommen und damit zweitens die Klammern richtig zu setzen, da mir die Anhaltspunkte fehlen. Catalan-Zahlen sind ja erst zum Testen nützlich…
Einfach ein paar Anhaltspunkte oder Orientierungspunkte wären wirklich hilfreich…
1 Like
Es ist leichter wenn man längere Strings betrachtet.
Wie kann man “abcd” aufteilen?
a,bcd Rekursion für bcd
ab,cd Rekursion für beide
abc,d Rekursion für abc
Beim Fall a,bcd gibt es die Klammerungen:
abcd, (a)bcd, a(bcd), (a)(bcd)
Hätte trotzdem noch jemand ein paar Gedankenanstöße für Klammern…komm nicht weiter…
Ich versteh nicht wie man man das aufteilen soll. Macht man rekursive Aufrufe, dann bekommt man eine Liste zurück. macht man das mit einem substring ist der teil den man vorher raus hat nicht mehr enthalten.
Dann noch klammern wie zum Beispiel ((a)(b)),
oder (a)(b(c))
Oder sonstiges was euch geholfen hat, oder für euch ein knackpunkt war…
Danke in voraus…
Du musst alle möglichen Klammerungen des linken Ausdrucks mit allen möglichen Klammerungen des rechten Ausdrucks kombinieren.
Beispiel: “ab” aufteilen in (“a”, “b”). Mögliche Klammerungen für den linken Teil (“a”) sind “(a)” und “a”. Mögliche Klammerungen für den rechten Teil (“b”) sind “(b)” und “b”. Alle möglichen Kombinationen davon sind “(a)(b)”, “(a)b”, “a(b)” und “ab”. Diese Kombinationen jeweils einmal mit und einmal ohne Klammer (“((a)(b))”, “((a)b)”, “(a(b))”, “(ab)”, “(a)(b)”, “(a)b”, “a(b)” und “ab”) ergeben die möglichen Klammerungen.
Ich bin auch weiterhin gleichermaßen verwirrt. Wie mein Vorredner schon schrieb, bekomme ich in der Rekursion ja immer eine Liste. Okay, die kann ich mit flatten bearbeiten, aber so fehlen mir doch Teile aus dem String, wenn ich nur einen Teil des Wortes weitergebe…
Benutzt ihr Hilfsfunktionen oder kommt man ohne aus?
Wenn du die Rekursion auf die zwei Teile eines Strings anwendest, kriegst du somit zwei Listen. Überleg mal, ob du da nicht eine Listenabstraktion einsetzen kannst, um alle Möglichkeiten zu ermitteln.
Hm, da müsste man doch einfach nur beide Listen in eine for comprehension bringen? Aber irgendwas mache ich da auch wieder falsch, denn das Ergebnis ist jetzt Liste a rangeklatscht an Liste b und nicht die Elemente von a und Elemente von b -.-’ Irgendwie verstehe ich Scala immer weniger anstatt immer mehr
Okay, ich nehme zurück, dass ich nicht verstehe, was da passiert. Ich kanns nur irgendwie nicht ändern 
Eventuell hilft das:
scala> val as = List.range(1, 5)
as: List[Int] = List(1, 2, 3, 4)
scala> val bs = List.range(6, 9)
bs: List[Int] = List(6, 7, 8)
scala> for (a <- as; b <- bs) yield (a, b)
res2: List[(Int, Int)] = List((1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,6), (3,7), (3,8), (4,6), (4,7), (4,8))Die Listenabstraktionen kannst du zum Beispiel so ähnlich einsetzen wie bei der [m]pairSums[/m]-Aufgabe auf dem gleichen Blatt. Um zwei Strings zusammenzufügen, kannst du einfach den [m]+[/m]-Operator verwenden. Ansonsten weiß ich leider gerade nicht, wo du genau hängst.
Hm, ich stehe wohl irgendwie auf dem Schlauch.
Wie die Listenabstraktion prinzipiell funktioniert verstehe ich und auch den + Operator kenne ich, aber wenn ich das versuche umzusetzen, bekomme ich zu viele Listenebenen und paare Listen mit Listen, mit flatten bekomme ich aber bei einer Liste dann nicht die Elemente einzeln sondern jedes Char einzeln (was auch logisch ist, aber leider nicht hilfreich).
Aber jetzt wird mir eh kein Geistesblitz mehr kommen, vielen Dank trotzdem für die vielen Tipps!!