# Klammerpermutation?



## tuxedo (24. Nov 2004)

Servus,
hab mal wieder ne tolle Aufgabe bekommen wo mir wieder n bisschen der Ansatz fehlt. Wie immer will ich keine Lösung von euch haben sondern einfach n paar Schlagwörter oder Ideen zur Aufgabe. 

Meine erste Idee zur Aufgabe war/ist daß es sich irgendwie um eine Art Permutation handelt. Aber hier gehts ja um klammern und nicht um zahlenreihenfolgen...



> Schreiben Sie ein Programm, welches eine natürliche Zahl n einliest und alle korrekt geklammerten
> Ausdrucke, bestehend aus n öffnenden und n schliessenden Klammern ausgibt. Die Zahl der
> gefundenen Klammerausdrücke soll zum Schluss ausgegeben werden. Schreiben Sie Ihr Programm
> ohne Verwendung von Rekursion! Für n = 3 soll die Ausgabe also wie folgt aussehen:
> ...




Gruß
Alex


----------



## Bleiglanz (24. Nov 2004)

nettes Problem, machs rekursiv

wenn n=1 dann gibts nur "()"

wenn n>1 dann erstelle die Liste für n-1 und nenne sie L

gib eine Liste zurück aus

"()"+ x sowie x + "()" sowie "("+x+")"

wobei x die Liste L durchläuft (nimm ein java.util.Set aus Strings, dann entstehen dabei auch keine Duplikate

vorsicht, stimmt vielleicht nicht, kommt mir jetzt zu einfach vor


----------



## tuxedo (25. Nov 2004)

Ja, rekursiv hätt ichs auch gemacht, aber ich MUSS es iterativ machen... Das ist ja mein Problem :-(
Mal sehen ob ich weiter komm'.

- Alex


----------



## Bleiglanz (25. Nov 2004)

das ist dämlich!

hier eine dämliche Lösung: 

iteriere über alle Bitfolgen der Länge 2n, interpretiere 0 als öffnende klammer, 1 als schliessende klammer

anzahl 0 und 1 ungleich => wegwerfen

über ein stackmodell prüfen, ob so ein ausdruck korrekt ist (also durchlaufen, für ein 0 ein X auf den Stack legen, für ein 1 ein X vom Stack runter -> am ende muss der Stack leer sein und wenn ein 1 kommt und der Stack leer ist gibts auch einen fehler)


----------

