Auf dieser Site gibt es einige Fragen zum Ausgleichen von Klammern und zum Überprüfen, ob die Klammern ausgewogen sind. Ich schlage vor, es ist jetzt Zeit, diese ausgewogenen Klammern für etwas zu verwenden!

In Mathematik und Programmierung sind Klammern wie Blasen, die alles Innere von allem Äußeren isolieren, sodass alles, was drinnen ist, in Ruhe seine Sache tun kann und alles, was draußen ist, nur ein Objekt sieht. Eine Reihe von Klammern ist jedoch eindimensional, während Blasen gewöhnlich mindestens zweidimensional sind. Das bedeutet, dass sich Blasen frei bewegen können, solange sie sich nicht berühren oder sich zwischen der Innenseite und der Außenseite anderer Blasen kreuzen.

Herausforderung

Die Eingabe ist eine Zeichenfolge aus aufeinander abgestimmten Klammern eines einzelnen Typs, entweder rund (), quadratisch [], geschweift {}oder winklig <>. Es liegt an Ihnen, welche Art von Programm Sie akzeptieren möchten, und ein Programm, das nur eine einzige Art von Klammern akzeptiert, wird akzeptiert. (Imaginärer Bonus, wenn Ihr Programm einen von ihnen verarbeiten kann, massive imaginäre Bonuspunkte, wenn es alle in derselben Eingabe verarbeiten kann.) Die Eingabe darf nichts zwischen den Klammern enthalten, obwohl abschließende Leerzeichen zulässig sind.

Bei der Ausgabe handelt es sich um alle möglichen Reorganisationen (in beliebiger Reihenfolge und einschließlich der ursprünglichen Eingabe) derjenigen Klammern, die dieselbe Blasenkonfiguration ohne zwei identische Zeichenfolgen ergeben. Das heißt, bei einer Eingabe von ()()ist die Ausgabe auch gerecht ()(), obwohl es technisch gesehen zwei Blasen sind, die Plätze tauschen könnten. Für den massiven imaginären Bonus führt eine Eingabe des {}[]()Willens natürlich zu einer Ausgabe von 6 verschiedenen Elementen / Strings / Linien.

Zwei Blasenkonfigurationen sind "gleich", wenn Sie eine Blase in die andere verschieben können, ohne dass sich eine Blase von innen nach außen oder von außen nach innen kreuzt. Wenn Sie verschachtelte Klammern mit Bäumen vergleichen (jedes übereinstimmende Paar ist ein Knoten, und jedes übereinstimmende Paar innerhalb ist ein Unterknoten, und jedes übereinstimmende Paar innerhalb ist wieder ein Unterknoten usw.), werden die Unterknoten eines bestimmten Knotens sortiert Dann ist eine einzelne Konfiguration von Blasen ein Baum, in dem die Knoten ungeordnet sind.

Jedes vernünftige Ausgabeformat reicht aus, z. B. das Zurückgeben einer Liste von Zeichenfolgen oder einer Liste von Einzelzeichen oder einer einzelnen Zeichenfolge mit einer Art von Leerzeichen oder das Drucken in stdoutoder stderrmit einer Form von sichtbarem Leerzeichen (meistens Zeilenvorschub oder Leerzeichen) dazwischen jede Neuorganisation.

Nachgestellte Leerzeichen für jede Reorganisation sowie nachgestellte und vorangestellte Zeilen / leere Listenelemente vor und nach der eigentlichen Ausgabe sind zulässig. Sie sollten in Ihrer Ausgabe die gleichen Klammern verwenden, die Sie in Ihrer Eingabe akzeptieren. Abgesehen von den hier angegebenen Klammern, Zeilenumbrüchen und Leerzeichen und dem von Ihnen verwendeten Trennzeichen sollte nichts gedruckt werden (einschließlich unsichtbarer / Null-Zeichen).

Die Punktzahl ist die Anzahl der Bytes im Code. Die niedrigste Anzahl für jede Sprache gewinnt. Sie können feststellen, ob Sie einen imaginären Bonus erhalten, entweder regulär oder massiv, aber dies hat keinen Einfluss auf Ihre Punktzahl. Tatsächliche Boni sind zu schwer auszugleichen.

Input-Output-Beispiele

Beispiel 1:

Eingang:

()(())

Ausgabe:

()(())
(())()

Beispiel 2:

Eingang:

(()())()()

Ausgabe:

(()())()()
()(()())()
()()(()())

Beispiel 3:

Eingang:

(()(()))()

Ausgabe:

((())())()
()((())())
(()(()))()
()(()(()))

CJam , 18 Bytes

{~{_{{B}%e!}&}:B~}

Probieren Sie es online!

-2 dank Business Cat .

Erhält Eingaben als Zeichenfolge, die nur enthält []. Gibt eine Liste mit Permutationen zurück (leere Listen sind die gleichen wie leere Zeichenfolgen in CJam, statt dass []Sie sie erhalten "").

Haskell , 227 210 208 205 Bytes

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

Probieren Sie es online!

Dieser war hart!

Ein bisschen Golf gespielt

Zwei Bytes dank Laikoni gespart

Sparen Sie zwei Bytes dank Bruce Forte

Ich bin mir nicht sicher, ob das in jedem Fall funktioniert. Einige Erklärungen:

• a!xfüge den String xder letzten Liste von Strings hinzu a(a ist vom Typ [[String]])

• snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])verwendet die kürzere Bedingung , um die einfache Idee auszudrücken: Teilen Sie einen String auf root )( s. ZB "(()(()))()"gibt ["()(())", ""].

• Wir müssen jeden Teil der Teilung verarbeiten, dann alle Zeichenfolgen sammeln und verbinden, um die richtige Ausgabe zu erhalten:

  1. hVerarbeitet eine Teileliste: Sie gilt vfür den ersten Teil und kombiniert das Ergebnis mit dem Prozess der übrigen Teile.

  2. v aggregiert die Ergebnisse für jede Permutation der Teile und entfernt die Duplikate.

Um eine umfassendere Ansicht hinzuzufügen: Sie haben im Grunde einen Baum (keinen binären) mit leeren Knoten. Urlaub sind (). Sie müssen für jeden Knoten alle Permutationen der Zweige erzeugen, dürfen jedoch keinen Zweig von einem Knoten nehmen und auf einen anderen Knoten legen. Ich habe eine Art Tiefensuche durchgeführt.

Python 2, 353 350 331 Bytes

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Erhält den String ()als Eingabe und druckt das Ergebnis.

Probieren Sie es hier aus!

Ich habe es vermieden, itertools.permutationsmit Hilfe von Paolo die Antwort auf diese Frage zu verwenden .

Vielen Dank an Business Cat für das Auffinden von 3 Bytes und an Mr. Xcoder für unglaubliche 19 Bytes!

Erläuterung

1. Erstellen Sie eine Liste von Tupeln der Indizes jedes ()Paars in der Eingabezeichenfolge.
2. Löschen Sie alle Tupel aus der Liste, die von einem anderen ()Paar umgeben sind.
3. Schneiden Sie die Zeichenfolge an den Indizes der verbleibenden Tupel.
4. Erstellen Sie eine Liste aller Permutationen der Liste der Slices.
5. Treten Sie der Liste mit einer neuen Zeile zum Drucken bei.

JavaScript (Firefox 30-57), 222 Byte

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Nimmt []Saiten. Erläuterung:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s

Mathematica, 337 Bytes

Nicht um Code-Golf-Punkte zu bekommen, sondern um die Verwendung von Permutationsund Distributein diesem Problem zu zeigen . Es kann jedoch bessere Ansätze geben.

( seq: Sequenz alt,: Alternativen)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Nehmen Sie die Eingabe in geschweiften Klammern {und als Zeichenfolge }. Ausgabe eines mehrzeiligen Strings.