9

^{Défi relevé d' ici et aussi ici}

Une séquence de n parenthèses se compose de n ( s et n ) s.

Une séquence de parenthèses valide est définie comme suit:

Vous pouvez trouver un moyen de répéter l'effacement de la paire de parenthèses adjacentes "()" jusqu'à ce qu'elle devienne vide.

Par exemple, (())est une parenthèse valide, vous pouvez effacer la paire en 2e et 3e position et elle devient (), puis vous pouvez la rendre vide. )()(n'est pas une parenthèse valide, après avoir effacé la paire en 2e et 3e position, elle devient )(et vous ne pouvez plus effacer

Tâche

Étant donné un nombre n, vous devez générer toutes les séquences de parenthèses correctes dans l' ordre lexicographique

La sortie peut être un tableau, une liste ou une chaîne (dans ce cas, une séquence par ligne)

Vous pouvez utiliser une autre paire de parenthèses, comme {}, [], ()ou tout signe d' ouverture-fermeture

Exemple

n = 3

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

n = 2
```
(())
()()
```

code-golf balanced-string Luis felipe De jesus Munoz
la source

@JoKing Oui bien sûr. Je suppose que cela ne changera en rien le concept principal du défi.

Luis felipe De jesus Munoz

Eh, je peux penser à quelques langues où eval les interpréterait différemment par exemple

Jo King

1

Connexes: numéros catalans (résultat de ce défi = nombre de lignes de résultat de ce défi)

user202729

3

Pratiquement les mêmes , mais avec des restrictions étranges comme "Vous ne pouvez pas écrire de fonctions récursives". /// Un sur-ensemble de ce défi (autoriser tous les supports Brain-Flak)

user202729

Est-ce qu'un "tableau, une liste ou une chaîne" "de séquences" de "n'importe quel signe d'ouverture-fermeture" signifie que nous pourrions produire une liste de listes de deux entiers (comme 1s et -1s)?

Jonathan Allan

8

Perl 6 , 36 octets

{grep {try !.EVAL},[X~] <[ ]>xx$_*2}

Essayez-le en ligne!

Trouve toutes les combinaisons triées lexographiquement de $2n$ [] s et filtre celles qui fonctionnent EVALcorrectement. Notez que toutes les combinaisons valides (même des trucs comme [][]) évaluent à [](ce qui est falsey, mais nous notle ( !) pour distinguer du tryretour Nil)

Explication:

{                                  }  # Anonymous code block
                        <[ ]>         # Create a list of ("[", "]")
                             xx$_*2   # Duplicate this 2n times
                   [X~]               # Find all possible combinations
 grep {          },                   # Filter from these
            .EVAL                     # The EVAL'd strings
       try !                          # That do not throw an error

Jo King
la source

3

Si quelqu'un est curieux, [][]c'est la tranche zen d'un tableau vide qui donne le tableau lui-même. La tranche peut être appliquée plusieurs fois, donc est [][][][]...évaluée à []. De plus, [[]]ne construit pas un tableau imbriqué mais un tableau vide à cause de la règle d'argument unique (vous devrez écrire [[],]pour un tableau imbriqué). Ainsi, toute séquence équilibrée de []parenthèses se traduit par un tableau vide qui devient booléen.

nwellnhof

6

R , 112 107 99 octets

Approche non récursive. Nous utilisons "<" et ">" car cela évite les caractères d'échappement dans l'expression régulière. Pour nous permettre d'utiliser une spécification plus courte pour une plage ASCII, nous générons 3 ^ 2n chaînes de 2n caractères de "<", "=" et ">" en utilisant expand.grid(via leurs codes ASCII 60, 61 et 62), puis grep pour voir quelles combinaisons donnent des crochets ouverts et fermés équilibrés. Les possibilités "=" seront ignorées, bien sûr.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(<(?1)*>)(?1)*$",apply(expand.grid(rep(list(60:62),2*n)),1,intToUtf8),,T,T))

Essayez-le en ligne!

Explication

"^(<(?1)*>)(?1)*$" = regex for balanced <> with no other characters
^ # match a start of the string
  ( # start of expression 1
    < # open <>
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    > # close <>
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(<(?1)*>)(?1)*$", # search for regular expression matching open and close brackets
      apply(
        expand.grid(rep(list(60:62),2*n)) # generate 3^(2n) 60,61,62 combinations
      ,1,intToUtf8) # turn into all 3^(2n) combinations of "<","=",">"
    ,,T,T) # return the values that match the regex, so "=" gets ignored
  ) # sort them

R , 107 octets

Approche récursive habituelle.

-1 merci @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

Essayez-le en ligne!

J.Doe
la source

1

ah, j'essayais de trouver un Mapgolf mais je ne pouvais pas en faire le tour. Je ne suis pas convaincu que parse+ evalfonctionnera depuis ()()et les erreurs de lancement similaires.

Giuseppe

4

C (gcc) , 114 octets

f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}

Essayez-le en ligne!

Devrait fonctionner pour n <= 15.

Explication

f(n,x,s,a,i){
  char b[99]={};   // Output buffer initialized with zeros.
  n*=2;            // Double n.
  for(x=1<<n;x--;  // Loop from x=2**n-1 to 0, x is a bit field
                   // where 1 represents '(' and 0 represents ')'.
                   // This guarantees lexicographical order.
      s|a<0||puts(b))  // Print buffer if s==0 (as many opening as
                       // closing parens) and a>=0 (number of open
                       // parens never drops below zero).
    for(s=a=i=0;i<n;)  // Loop from i=0 to n-1, note that we're
                       // traversing the bit field right-to-left.
      a|=              // a is the or-sum of all intermediate sums,
                       // it becomes negative whenever an intermediate
                       // sum is negative.
        s+=            // s is the number of closing parens minus the
                       // number of opening parens.
                        x>>i++&1   // Isolate current bit and inc i.
                    41-(        )  // ASCII code of paren, a one bit
                                   // yields 40 '(', a zero bit 41 ')'.
             b[n-i]=               // Store ASCII code in buffer.
          2*(                    )-81;  // 1 for ')' and -1 for '(' since
                                        // we're going right-to-left.
}

nwellnhof
la source

4

Python 2 , 91 88 84 81 octets

f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']

Essayez-le en ligne!

_{-3 octets grâce aux pizzapants184}

TFeld
la source

Fonctionne

Vous pouvez le remplacer set(...)par un ensemble comprehension ( {...}) pour -3 octets Essayez-le en ligne!

pizzapants184

@ pizzapants184 Merci :)

TFeld

3

05AB1E , 13 octets

„()©s·ãʒ®õ:õQ

Essayez-le en ligne ou vérifiez d'autres cas de test .

Explication:

„()            # Push string "()"
   ©           # Store it in the register without popping
    s·         # Swap to get the (implicit) input, and double it
      ã        # Cartesian product that many times
       ʒ       # Filter it by:
        ®      #  Push the "()" from the register
         õ:    #  Infinite replacement with an empty string
           õQ  #  And only keep those which are empty after the infinite replacement

Kevin Cruijssen
la source

3

Ruby , 70 octets

f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|[]}

Essayez-le en ligne!

GB
la source

3

Japt, 15 13 octets

ç>i<)á Ôke/<>

Essayez-le

Explication

ç                 :Input times repeat the following string
 >i<              :  ">" prepended with "<"
    )             :End repeat
     á            :Get unique permutations
       Ô          :Reverse
        k         :Remove any that return true (non-empty string)
         e/<>     :  Recursively replace Regex /<>/

Hirsute
la source

3

K (ngn / k) , 36 35 octets

{"()"(&/-1<+\1-2*)#(x=+/)#+!2|&2*x}

Essayez-le en ligne!

+!2|&2*x tous les vecteurs binaires de longueur 2 * n

(x=+/)# seulement ceux qui résument à n

(&/-1<+\1-2*)# seuls ceux dont les sommes partielles, traitant 0/1 comme 1 / -1, ne sont nulle part négatives

"()" utiliser 0/1 comme index dans cette chaîne

ngn
la source

2

Perl 5 `-n` , 41 39 octets

-2 octets avec équerres

s/<(?R)*>//gr||say for glob'{<,>}'x2x$_

Essayez-le en ligne!

Port de ma réponse Perl 6.

nwellnhof
la source

2

Perl 6 , 42 octets

{grep {!S:g/\(<~~>*\)//},[X~] <( )>xx$_*2}

Essayez-le en ligne!

Utilise une expression régulière récursive. Substitution alternative:S/[$<~~>$]*//

38 octets avec 0 et 1 comme symboles d'ouverture / fermeture:

{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}

Essayez-le en ligne!

Explication

{                                        }  # Anonymous block
                              <( )>         # List "(", ")"
                                   xx$_*2   # repeated 2n times
                         [X~]  # Cartesian product with string concat
                               # yields all strings of length 2n
                               # consisting of ( and )
 grep {                },  # Filter strings
        S:g/             # Globally replace regex match
            \(           #   literal (
              <~~>       #   whole regex matched recursively
                  *      #   zero or more times
                   \)    #   literal )
                     //  # with empty string
       !                 # Is empty string?

nwellnhof
la source

2

Retina 0.8.2 , 50 octets

.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)

Essayez-le en ligne! Utilise l' <>art. Explication:

.+
$*

Convertissez en unaire.

1
11

Doublez le résultat.

+%1`1
<$'¶$`>

Énumérer tous les nombres binaires 2²ⁿ 2n bits, en mappant les chiffres sur <>.

Gm`^(?<-1>(<)*>)*$(?(1).)

Ne gardez que des séquences équilibrées. Cela utilise une astuce entre parenthèses équilibrée découverte par @MartinEnder.

Neil
la source

2

JavaScript (ES6), 112 102 octets

Ceci est fortement basé sur la réponse C de nwellnhof .

f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)

Essayez-le en ligne!

Arnauld
la source

2

Rouge , 214, 184136 octets

func[n][g: func[b n][either n = length? b[if not error? try[load b][print b]return 0][g append copy b"["n g append copy b"]"n]]g""2 * n]

Essayez-le en ligne!

Utilise l'approche de Jo King. Recherche tous les arrangements possibles de crochets en utilisant la récursivité (ils sont générés dans l'ordre lexicographique) et l'imprime si l'arrangement est évalué comme un bloc valide.

Galen Ivanov
la source

1

Gelée , 19 octets

Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(

Essayez-le en ligne!

Sortie clarifiée sur TIO.

Erik le Outgolfer
la source

Séquences entre parenthèses dans l'ordre lexicographique

Réponses:

Perl 6 , 36 octets

Explication:

R , 112 107 99 octets

Explication

R , 107 octets

C (gcc) , 114 octets

Explication

Python 2 , 91 88 84 81 octets

05AB1E , 13 octets

Ruby , 70 octets

Japt, 15 13 octets

Explication

K (ngn / k) , 36 35 octets

Perl 5 `-n` , 41 39 octets

Perl 6 , 42 octets

Explication

Retina 0.8.2 , 50 octets

JavaScript (ES6), 112 102 octets

Rouge , 214, 184136 octets

Gelée , 19 octets

Séquences entre parenthèses dans l'ordre lexicographique

Réponses:

Perl 6 , 36 octets

Explication:

R , 112 107 99 octets

Explication

R , 107 octets

C (gcc) , 114 octets

Explication

Python 2 , 91 88 84 81 octets

05AB1E , 13 octets

Ruby , 70 octets

Japt, 15 13 octets

Explication

K (ngn / k) , 36 35 octets

Perl 5 -n , 41 39 octets

Perl 6 , 42 octets

Explication

Retina 0.8.2 , 50 octets

JavaScript (ES6), 112 102 octets

Rouge , 214, 184136 octets

Gelée , 19 octets

Perl 5 `-n` , 41 39 octets