^{Reto tomado desde aquí y también aquí}

Una secuencia de n paréntesis consta de n ( sy n ) s.

Una secuencia de paréntesis válida se define como la siguiente:

Puede encontrar una manera de repetir el borrado de par de paréntesis adyacentes "()" hasta que quede vacío.

Por ejemplo, (())es un paréntesis válido, puede borrar el par en la segunda y tercera posición y se convierte (), luego puede dejarlo vacío. )()(no es un paréntesis válido, después de borrar el par en la segunda y tercera posición, se convierte en )(y no puede borrar más

Tarea

Dado un número n , necesita generar toda la secuencia correcta de paréntesis en orden lexicográfico

La salida puede ser una matriz, lista o cadena (en este caso, una secuencia por línea)

Se puede usar un par diferente de paréntesis como {}, [], ()o cualquier signo de apertura y cierre

Ejemplo

• n = 3

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

• n = 2

  (())
  ()()
  

Perl 6 , 36 bytes

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

Pruébalo en línea!

Encuentra todas las combinaciones ordenadas lexográficamente de sy filtra las que están correctamente. Tenga en cuenta que todas las combinaciones válidas (incluso cosas como ) evalúan a (que es falsey, pero nosotros ( ) para distinguir de regresar )$2n$ []EVAL[][][]not!tryNil

Explicación:

{                                  }  # 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

R , 112 107 99 bytes

Enfoque no recursivo. Usamos "<" y ">" porque evita los caracteres de escape en la expresión regular. Para permitirnos usar una especificación más corta para un rango ASCII, generamos 3 ^ 2n cadenas de 2n caracteres de "<", "=" y ">" usando expand.grid(a través de sus códigos ASCII 60, 61 y 62) y luego grep para vea qué combinaciones dan corchetes abiertos y cerrados equilibrados. Las posibilidades "=" serán ignoradas, por supuesto.

Vía 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))

Pruébalo en línea!

Explicación

"^(<(?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 bytes

Enfoque recursivo habitual.

-1 gracias @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))

Pruébalo en línea!

C (gcc) , 114 bytes

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;}

Pruébalo en línea!

Debería funcionar para n <= 15.

Explicación

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.
}

Python 2 , 91 88 84 81 bytes

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

Pruébalo en línea!

_{-3 bytes gracias a pizzapants184}

05AB1E , 13 bytes

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

Pruébelo en línea o verifique algunos casos de prueba más .

Explicación:

„()            # 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

Ruby , 70 bytes

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

Pruébalo en línea!

Japt, 15 13 bytes

ç>i<)á Ôke/<>

Intentalo

Explicación

ç                 :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 /<>/

K (ngn / k) , 36 35 bytes

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

Pruébalo en línea!

+!2|&2*x todos los vectores binarios de longitud 2 * n

(x=+/)# solo aquellos que suman n

(&/-1<+\1-2*)# solo aquellos cuyas sumas parciales, tratando 0/1 como 1 / -1, no son negativas

"()" use 0/1 como índices en esta cadena

Perl 5 -n , 41 39 bytes

-2 bytes con paréntesis angulares

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

Pruébalo en línea!

Puerto de mi Perl 6 respuesta.

Perl 6 , 42 bytes

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

Pruébalo en línea!

Utiliza una expresión regular recursiva. Sustitución alternativa:S/[\(<~~>\)]*//

38 bytes con 0 y 1 como símbolos de apertura / cierre:

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

Pruébalo en línea!

Explicación

{                                        }  # 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?

Retina 0.8.2 , 50 bytes

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

Pruébalo en línea! Usos <>s. Explicación:

.+
$*

Convierte a unario.

1
11

Duplica el resultado.

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

Enumere todos los números binarios de 2²ⁿ 2n bits, asignando los dígitos a <>.

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

Mantenga solo secuencias equilibradas. Utiliza un truco de paréntesis equilibrado descubierto por @MartinEnder.

JavaScript (ES6), 112 102 bytes

Esto se basa en gran medida en la respuesta 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)

Pruébalo en línea!

Rojo , 214, 184 136 bytes

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]

Pruébalo en línea!

Utiliza el enfoque de Jo King. Encuentra todos los arreglos posibles de paréntesis utilizando la recursividad (se generan en orden lexicográfico) e imprímelo si el arreglo se evalúa como un bloque válido.

Jalea , 19 bytes

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

Pruébalo en línea!

Salida aclarada sobre TIO.