Il y a quelques questions sur ce site concernant l'équilibrage des supports et la vérification de l'équilibre des supports. Je propose qu'il soit maintenant temps d'utiliser ces supports équilibrés pour quelque chose!

En mathématiques et en programmation, les parenthèses sont comme des bulles, isolant tout à l'intérieur de tout à l'extérieur de sorte que tout ce qui est à l'intérieur puisse faire son travail en paix et tout ce qui est à l'extérieur ne voit qu'un seul objet. Cependant, une chaîne de parenthèses est unidimensionnelle, tandis que les bulles sont généralement au moins bidimensionnelles. Cela signifie que les bulles sont libres de se déplacer les unes les autres tant qu'elles ne se touchent jamais ou ne se croisent pas entre l'intérieur et l'extérieur d'autres bulles.

Défi

L'entrée est une chaîne de crochets assortis d'un seul type, soit ronde (), carrée [], bouclée {}ou angulaire <>. C'est à vous de décider quel type vous voulez que votre programme accepte, et un programme qui n'accepte qu'un seul type de parenthèses est accepté. (Bonus imaginaire si votre programme peut gérer l'un d'eux, des points bonus imaginaires massifs s'il peut tous les gérer dans la même entrée.) L'entrée ne peut rien contenir entre les crochets, bien que les espaces de fin soient autorisés.

La sortie est toutes les réorganisations possibles (dans un ordre arbitraire, et y compris l'entrée d'origine) de ces crochets qui donne la même configuration de bulles, sans deux chaînes identiques. Cela signifie qu'avec une entrée de ()(), la sortie est également juste ()(), même si ce sont techniquement deux bulles qui pourraient changer de place. Pour le bonus imaginaire massif, une entrée de {}[]()volonté conduira bien sûr à une sortie de 6 éléments / cordes / lignes différents.

Deux configurations de bulles sont "les mêmes" si vous pouvez les faire l'une dans l'autre en déplaçant les bulles, sans laisser aucune bulle passer de l'intérieur d'une autre bulle à l'extérieur, ou de l'extérieur à l'intérieur. Si vous comparez des parenthèses imbriquées à des arbres (chaque paire correspondante est un nœud, et chaque paire correspondante à l'intérieur est un sous-nœud, et chaque paire correspondante à l'intérieur est à nouveau un sous-nœud de ceux-ci, etc.) où les sous-nœuds d'un nœud donné sont ordonnés , alors une seule configuration de bulles est un arbre où les nœuds ne sont pas ordonnés.

Tout format de sortie raisonnable fera l'affaire, comme renvoyer une liste de chaînes ou une liste de liste de caractères uniques ou une seule chaîne avec une sorte d'espace blanc, ou imprimer vers stdoutou stderravec une forme de caractère d'espace blanc visible (le plus souvent une nouvelle ligne ou un espace) entre chaque réorganisation.

Les espaces de fin pour chaque réorganisation et les éléments de liste / vides de fin et de précédant avant et après la sortie réelle sont autorisés. Vous devez utiliser le même type de parenthèses dans votre sortie que vous acceptez dans votre entrée. Hormis les crochets, les retours à la ligne et les espaces spécifiés ici, et quel que soit le séparateur que vous utilisez, rien ne doit être imprimé (y compris les caractères invisibles / de largeur nulle).

Le score est le nombre d'octets dans le code; le décompte le plus bas pour chaque langue gagne. Vous pouvez noter si vous obtenez un bonus imaginaire, régulier ou massif, mais cela n'affecte pas votre score. Les bonus réels sont trop difficiles à équilibrer correctement.

Exemples d'entrées-sorties

Exemple 1:

Contribution:

()(())

Sortie:

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

Exemple 2:

Contribution:

(()())()()

Sortie:

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

Exemple 3:

Contribution:

(()(()))()

Sortie:

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

CJam , 18 octets

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

Essayez-le en ligne!

-2 grâce à Business Cat .

Reçoit l'entrée sous la forme d'une chaîne contenant uniquement []. Renvoie une liste de permutations (les listes vides sont les mêmes que les chaînes vides dans CJam, donc au lieu de []vous obtenez "").

Haskell , 227 210 208 205 octets

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)

Essayez-le en ligne!

Celui-ci était difficile!

Golfé un peu

Enregistré deux octets grâce à Laikoni

Économisez deux octets grâce à Bruce Forte

Je ne suis pas sûr que cela fonctionne dans tous les cas. Quelques explications:

• a!xajouter la chaîne xà la dernière liste de chaînes dans a(un est de 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])utilise le conditionnel plus court pour exprimer l'idée simple: diviser une chaîne à la racine )( s. Par exemple, "(()(()))()"donne ["()(())", ""].

• Nous devons traiter chaque partie du fractionnement, puis rassembler et joindre toutes les chaînes pour obtenir la sortie correcte:

  1. htraite une liste de pièces: il s'applique và la première pièce et combine le résultat au traitement des pièces restantes.

  2. v agrège les résultats pour chaque permutation des pièces et supprime les doublons.

Pour ajouter une vue plus large: vous avez essentiellement un arbre (pas binaire) avec des nœuds vides. Laissez (). Vous devez produire toutes les permutations des branches pour chaque nœud, mais vous ne pouvez pas prendre une branche d'un nœud et la placer sur un autre nœud. J'ai fait une sorte de première recherche approfondie.

Python 2, 353 350 331 octets

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

Reçoit une chaîne ()en entrée et imprime le résultat.

Essayez-le ici!

J'ai évité d'utiliser itertools.permutationsavec l'aide de la réponse de Paolo à cette question .

Merci à Business Cat d' avoir trouvé 3 octets, et merci à M. Xcoder pour un incroyable 19 octets!

Explication

1. Créez une liste de tuples des indices de chaque ()paire dans la chaîne d'entrée.
2. Supprimez tous les tuples de la liste qui sont entourés par une autre ()paire.
3. Coupez la chaîne aux indices des tuples restants.
4. Faites une liste de chaque permutation de la liste des tranches.
5. Rejoignez la liste avec une nouvelle ligne pour l'impression.

JavaScript (Firefox 30-57), 222 octets

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

Prend des []cordes. Explication:

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 octets

Pas pour obtenir des points de golf, mais pour montrer l'utilisation de Permutationset Distributedans ce problème. Il peut cependant y avoir de meilleures approches.

( seq: séquence,: altalternatives)

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

Prenez l'entrée comme une chaîne, en utilisant des accolades {et }. Génère une chaîne multi-lignes.