Não são algumas perguntas sobre este site sobre o equilíbrio entre parênteses, e verificar se os suportes estão equilibradas. Proponho que agora é hora de usar esses colchetes equilibrados para alguma coisa!

Em matemática e programação, os colchetes são como bolhas, isolando tudo de dentro, forma tudo de fora, para que tudo o que está dentro possa fazer suas coisas em paz e o que estiver fora veja apenas um objeto. No entanto, uma série de colchetes é unidimensional, enquanto as bolhas geralmente são pelo menos bidimensionais. Isso significa que as bolhas são livres para se movimentar, desde que nunca se toquem ou se cruzem entre o interior e o exterior de quaisquer outras bolhas.

Desafio

A entrada é uma sequência de colchetes correspondentes de um único tipo, redondo (), quadrado [], ondulado {}ou angular <>. Depende de você o tipo que você deseja que seu programa aceite, e um programa que aceita apenas um único tipo de colchete é aceito. (Bônus imaginário se o seu programa puder lidar com qualquer um deles, pontos de bônus imaginários maciços se ele puder lidar com todos eles na mesma entrada.) A entrada não pode conter nada entre os colchetes, embora espaços em branco à direita sejam permitidos.

A saída é todas as reorganizações possíveis (em ordem arbitrária e incluindo a entrada original) daqueles colchetes que produzem a mesma configuração de bolhas, sem duas seqüências idênticas. Isso significa que, com uma entrada de ()(), a saída também é justa ()(), apesar de serem tecnicamente duas bolhas que poderiam trocar de lugar. Para o bônus imaginário maciço, {}[]()é claro que uma entrada de vontade leva a uma saída de 6 elementos / strings / linhas diferentes.

Duas configurações de bolhas são "iguais" se você puder se transformar uma na outra movendo as bolhas, sem deixar nenhuma bolha passar de dentro de outra bolha para fora dela ou de fora para dentro. Se você comparar parênteses aninhados a árvores (cada par correspondido é um nó e todo par correspondido dentro de um subnó, e cada par correspondido dentro de um subnó desses novamente, e assim por diante) em que os subnós de qualquer nó são ordenados , uma única configuração de bolhas é uma árvore na qual os nós não são ordenados.

Qualquer formato de saída razoável funcionará, como retornar uma lista de cadeias de caracteres ou uma lista de caracteres únicos ou uma única string com algum tipo de espaço em branco ou imprimir em stdoutou stderrcom alguma forma de caractere visível do espaço em branco (geralmente nova linha ou espaço) entre cada reorganização.

Espaços finais para cada reorganização e linhas novas / elementos à esquerda e à lista vazias anteriores e anteriores à saída real são permitidas. Você deve usar o mesmo tipo de colchetes na saída que aceita na entrada. Além dos colchetes, das novas linhas e dos espaços especificados aqui, e do separador usado, nada deve ser impresso (incluindo caracteres invisíveis / largura zero).

A pontuação é o número de bytes no código; a contagem mais baixa para cada idioma vence. Você pode observar se recebe um bônus imaginário, regular ou massivo, mas isso não afeta sua pontuação. Os bônus reais são muito difíceis de equilibrar corretamente.

Exemplos de entrada e saída

Exemplo 1:

Entrada:

()(())

Saída:

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

Exemplo 2:

Entrada:

(()())()()

Saída:

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

Exemplo 3:

Entrada:

(()(()))()

Saída:

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

CJam , 18 bytes

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

Experimente online!

-2 graças ao Business Cat .

Recebe entrada como uma string contendo apenas []. Retorna uma lista de permutações (listas vazias são iguais às cadeias vazias no CJam, portanto, em vez de []você obter "").

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)

Experimente online!

Este foi difícil!

Jogou um pouco de golfe

Economizou dois bytes graças a Laikoni

Economize dois bytes graças a Bruce Forte

Não tenho certeza se isso funciona em todos os casos. Algumas explicações:

• a!xadicione a String xà última lista de String em a(a é do 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 a condicional mais curta para expressar a idéia simples: divida uma String na raiz )( s. Por exemplo, "(()(()))()"dá ["()(())", ""].

• Precisamos processar cada parte da divisão e, em seguida, reunir e juntar todas as strings para obter a saída correta:

  1. hprocessa uma lista de partes: aplica-se và primeira parte e combina o resultado ao processo das partes restantes.

  2. v agrega os resultados para cada permutação das partes e remove as duplicatas.

Para adicionar uma visão mais ampla: você tem basicamente uma árvore (não uma binária) com nós vazios. Deixe são (). É necessário produzir todas as permutações dos ramos para cada nó, mas você não pode pegar um ramo de um nó e colocá-lo em outro nó. Eu fiz uma espécie de profundidade primeira pesquisa.

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

Recebe a string ()como entrada e imprime o resultado.

Experimente aqui!

Evitei usar itertools.permutationscom a ajuda da resposta de Paolo a esta pergunta .

Obrigado ao Business Cat por encontrar 3 bytes e obrigado ao Sr. Xcoder por incríveis 19 bytes!

Explicação

1. Crie uma lista de tuplas dos índices de cada ()par na sequência de entrada.
2. Solte as tuplas da lista cercadas por outro ()par.
3. Corte a corda nos índices das tuplas restantes.
4. Faça uma lista de cada permutação da lista de fatias.
5. Entre na lista com uma nova linha para impressão.

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 []seqüências de caracteres. Explicação:

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

Não para obter pontos de código-golfe, mas para mostrar o uso Permutationse Distributeneste problema. Pode haver abordagens melhores, no entanto.

( seq: sequência,: altalternativas)

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 entrada como uma string, usando colchetes {e }. Saída de uma seqüência de linhas múltiplas.