Bubble the brackets!

Question

There are a few questions on this site about balancing brackets, and checking whether brackets are balanced. I propose it's now time to use those balanced brackets for something!

In mathematics and programming, brackets are like bubbles, isolating everything inside form everything outside so that whatever's inside can do its thing in peace and whatever's outside only sees one object. However, a string of brackets is one-dimensional, while bubbles usually are at least two dimensional. That means that bubbles are free to move around one another as long as they never touch each other or cross between the inside and the outside of any other bubbles.

Challenge

The input is a string of matched brackets of a single type, either round (), square [], curly {} or angle <>. It's up to you what kind you want your program to accept, and a program that only accepts a single kind of brackets is accepted. (Imaginary bonus if your program can handle any of them, massive imaginary bonus points if it can handle all of them in the same input.) The input cannot contain anything between the brackets, although trailing whitespaces are allowed.

The output is all possible reorganisations (in arbitrary order, and including the original input) of those brackets that yields the same configuration of bubbles, with no two identical strings. That means that with an input of ()(), the output is also just ()(), even though it's technically two bubbles that could swap places. For the massive imaginary bonus, an input of {}[]() will of course lead to an output of 6 different elements / strings / lines.

Two configurations of bubbles are "the same" if you can make one into the other by moving bubbles around, without letting any bubble cross from inside another bubble to outside it, or from outside to inside. If you liken nested parentheses to trees (each matched pair is one node, and every matched pair within is a subnode, and each matched pair within there is a subnode of those again, and so on) where the subnodes of any given node are ordered, then a single configuration of bubbles is a tree where the nodes are unordered.

Any reasonable output format will do, like returning a list of strings or a list of list of single characters or a single string with some kind of whitespace, or printing to stdoutor stderr with some form of visible whitespace character (most commonly newline or space) between each reorganisation.

Trailing spaces for each reorganisation and trailing and preceeding newlines / empty list elements before and after the actual output is allowed. You should use the same kind of brackets in your output as you accept in your input. Apart from the brackets, newlines and spaces as specified here, and whatever separator you use, nothing should be printed (including invisible / zero-width characters).

The score is the number of bytes in the code; lowest count for each language wins. You may note whether you get an imaginary bonus, either regular or massive, but it doesn't affect your score. Actual bonuses are too hard to balance right.

Input-output examples

Example 1:

Input:

()(())

Output:

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

Example 2:

Input:

(()())()()

Output:

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

Example 3:

Input:

(()(()))()

Output:

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

Answer 1

CJam, 18 bytes

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

Try it online!

-2 thanks to Business Cat.

Receives input as a string containing only []. Returns a list of permutations (empty lists are the same as empty strings in CJam, so instead of [] you'll be getting "").

Answer 2

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)

Try it online!

This one was tough!

Golfed a little bit

Saved two bytes thanks to Laikoni

Save two bytes thanks to Bruce Forte

I'm not sure this works in every case. Some explanations:

• a!x add the String x to the last list of String in a (a is of type [[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]) uses the shorter conditional to express the simple idea: split a String on root )(s. E.g. "(()(()))()" gives ["()(())", ""].

• We need to process each part of the split, then to gather and join all the strings to get the correct output:

  1. h processs a list of parts: it applies v to the first part and combines the result to the process of the remaining parts.

  2. v aggregates the results for each permutation of the parts, and remove the duplicates.

To add a broader view: you have basically a tree (not a binary one) with empty nodes. Leave are (). You have to produce all the permutations of the branches for each node, but you may not take a branch from a node and put it on another node. I did a kind of depth first search.

Answer 3

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])])]

Receives string of () as input and prints the result.

Try it here!

I avoided using itertools.permutations with help from Paolo's answer to this question.

Thank you to Business Cat for finding 3 bytes, and thank you to Mr. Xcoder for an incredible 19 bytes!

Explanation

1. Create a list of tuples of the indices of each () pair in the input string.
2. Drop any tuples from the list that are surrounded by another () pair.
3. Slice the string at the indices of the remaining tuples.
4. Make a list of each permutation of the list of slices.
5. Join the list with a new line for printing.

Answer 4

JavaScript (Firefox 30-57), 222 bytes

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))

Takes [] strings. Explanation:

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

Answer 5

Mathematica, 337 bytes

Not to get code-golf points, but to show the usage of Permutations and Distribute in this problem. There may be better approaches, though.

(seq : sequence, alt : alternatives)

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}] &

Take input as a string, using curly brackets { and }. Output a multi-line string.