No son unas cuantas preguntas en este sitio sobre el equilibrio entre paréntesis, corchetes y comprobar si están equilibrados. ¡Propongo que es hora de usar esos soportes equilibrados para algo!

En matemáticas y programación, los corchetes son como burbujas, aislando todo lo que está dentro de todo lo que está afuera para que lo que esté adentro pueda hacer sus cosas en paz y lo que esté afuera solo vea un objeto. Sin embargo, una serie de paréntesis es unidimensional, mientras que las burbujas generalmente son al menos bidimensionales. Eso significa que las burbujas son libres de moverse entre sí, siempre y cuando nunca se toquen o crucen entre el interior y el exterior de cualquier otra burbuja.

Reto

La entrada es una cadena de corchetes coincidentes de un solo tipo, ya sea redondo (), cuadrado [], rizado {}o en ángulo <>. Depende de usted qué tipo desea que acepte su programa, y ​​se acepta un programa que solo acepta un solo tipo de paréntesis. (Bonificación imaginaria si su programa puede manejar cualquiera de ellos, puntos de bonificación imaginarios masivos si puede manejarlos a todos en la misma entrada.) La entrada no puede contener nada entre los corchetes, aunque se permiten espacios en blanco finales.

La salida es todas las posibles reorganizaciones (en orden arbitrario, e incluyendo la entrada original) de esos corchetes que producen la misma configuración de burbujas, sin dos cadenas idénticas. Eso significa que con una entrada de ()(), la salida también es justa ()(), aunque técnicamente son dos burbujas que podrían intercambiar lugares. Para el bono imaginario masivo, una entrada de {}[](), por supuesto, dará lugar a una salida de 6 elementos / cadenas / líneas diferentes.

Dos configuraciones de burbujas son "iguales" si puede hacer una en la otra moviendo las burbujas, sin permitir que ninguna burbuja se cruce desde el interior de otra burbuja hacia afuera, o desde afuera hacia adentro. Si compara los paréntesis anidados con los árboles (cada par coincidente es un nodo, y cada par coincidente dentro es un subnodo, y cada par coincidente dentro hay un subnodo de esos nuevamente, y así sucesivamente) donde se ordenan los subnodos de cualquier nodo dado , entonces una única configuración de burbujas es un árbol donde los nodos están desordenados.

Cualquier formato de salida razonable servirá, como devolver una lista de cadenas o una lista de caracteres individuales o una sola cadena con algún tipo de espacio en blanco, o imprimir stdouto stderrcon algún tipo de carácter de espacio en blanco visible (más comúnmente nueva línea o espacio) entre cada reorganización

Espacios finales para cada reorganización y elementos de nueva línea / lista vacía anteriores y posteriores antes y después de que se permita la salida real. Debe usar el mismo tipo de corchetes en su salida que acepta en su entrada. Aparte de los corchetes, las nuevas líneas y los espacios como se especifica aquí, y cualquier separador que use, no se debe imprimir nada (incluidos los caracteres invisibles / de ancho cero).

El puntaje es el número de bytes en el código; La cuenta más baja para cada idioma gana. Puede observar si obtiene un bono imaginario, ya sea regular o masivo, pero no afecta su puntaje. Las bonificaciones reales son demasiado difíciles de equilibrar correctamente.

Ejemplos de entrada-salida

Ejemplo 1:

Entrada:

()(())

Salida:

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

Ejemplo 2

Entrada:

(()())()()

Salida:

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

Ejemplo 3

Entrada:

(()(()))()

Salida:

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

CJam , 18 bytes

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

Pruébalo en línea!

-2 gracias a Business Cat .

Recibe la entrada como una cadena que contiene solo []. Devuelve una lista de permutaciones (las listas vacías son lo mismo que las cadenas vacías en CJam, por lo que en lugar de las []que obtendrá "").

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)

Pruébalo en línea!

Este fue duro!

Golfé un poco

Guardado dos bytes gracias a Laikoni

Ahorre dos bytes gracias a Bruce Forte

No estoy seguro de que esto funcione en todos los casos. Algunas explicaciones:

• a!xagregue la Cadena xa la última lista de Cadena en a(a es de tipo [[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])usa el condicional más corto para expresar la idea simple: dividir una cadena en la raíz )( s. Por ejemplo, "(()(()))()"da ["()(())", ""].

• Necesitamos procesar cada parte de la división, luego reunir y unir todas las cadenas para obtener la salida correcta:

  1. hprocesa una lista de partes: se aplica va la primera parte y combina el resultado con el proceso de las partes restantes.

  2. v agrega los resultados para cada permutación de las partes y elimina los duplicados.

Para agregar una vista más amplia: básicamente tiene un árbol (no binario) con nodos vacíos. Deja son (). Debe producir todas las permutaciones de las ramas para cada nodo, pero no puede tomar una rama de un nodo y colocarla en otro nodo. Hice una especie de primera búsqueda en profundidad.

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

Recibe una cadena de ()como entrada e imprime el resultado.

Pruébalo aquí!

Evité usar itertools.permutationscon la ayuda de la respuesta de Paolo a esta pregunta .

¡Gracias a Business Cat por encontrar 3 bytes, y gracias al Sr. Xcoder por sus increíbles 19 bytes!

Explicación

1. Cree una lista de tuplas de los índices de cada ()par en la cadena de entrada.
2. Elimine las tuplas de la lista que están rodeadas por otro ()par.
3. Corta la cuerda en los índices de las tuplas restantes.
4. Haga una lista de cada permutación de la lista de sectores.
5. Únase a la lista con una nueva línea para imprimir.

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

Toma []cuerdas. Explicación:

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

No para obtener puntos de código de golf, sino para mostrar el uso Permutationsy Distributeen este problema. Sin embargo, puede haber mejores enfoques.

( seq: secuencia alt,: alternativas)

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

Tome la entrada como una cadena, usando llaves {y }. Salida de una cadena de varias líneas.