Una cadena de *()[]llaves se define como una cadena que consiste en los caracteres en los que las llaves coinciden correctamente:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

Esta es una cadena de llaves válida:

((())***[]**)****[(())*]*

Pero estos no son:

)(
**(**[*](**)
**([*)]**

Su tarea es escribir un programa (o función) que, dado un número entero positivo n, tome un número como entrada y produzca (o devuelva) todas las cadenas de longitud válidas de llaves n.

Especificaciones

• Puede generar las cadenas en cualquier orden.
• Puede generar una lista o una cadena separada por un carácter diferente.
• Su programa debe manejar 0 correctamente. Hay 1 posible cadena de llaves de longitud 0, que es la cadena vacía "".
• Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .

Casos de prueba

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*

Jalea, 29 bytes

-3 bytes gracias a @JonathanAllan

¡Por favor , avísenme si hay problemas / errores / errores o bytes que pueda eliminar!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Pruébalo en línea!

Las soluciones anteriores que tuve:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Explicación (mi mejor intento en una descripción):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter

Prólogo, 69 bytes

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

Una de las propiedades más interesantes de Prolog es que en muchos casos es capaz de ejecutar un programa al revés; por ejemplo, en lugar de probar para ver si algo es cierto, puede generar todas las soluciones para las cuales es cierto, y en lugar de verificar la longitud de una cadena, puede generar todas las cadenas con una longitud determinada. (Otra buena propiedad de Prolog es que requiere un espacio en blanco después del final de cada definición de predicado, y se puede insertar una nueva línea tan barata como un espacio; por lo tanto, incluso los programas de golf a menudo son bastante legibles).

Lo anterior define un predicado (el equivalente de una función) bque prueba para ver si una cadena tiene una longitud determinada y es una "cadena de llaves" como se define en la pregunta. Específicamente, lo hace a través del soporte de gramática / expresión regular / coincidencia de patrones de Prolog que proporciona algo de azúcar breve y agradable para definir este tipo de expresión (aparentemente esto es estándar / portátil, pero no estaba al tanto de esto mientras escribía originalmente la respuesta, y por lo tanto asumió que la respuesta funcionaría en una sola implementación de Prolog; sin embargo, parece que funciona en cada implementación que cumpla con los estándares). El programa se puede traducir al inglés de manera bastante directa; las primeras dos líneas dicen "una s es una cadena vacía, o una e seguida de una s ; una ees un asterisco, o una s entre paréntesis, o una s entre corchetes ". La tercera línea puede interpretarse como" La b de N puede ser A si A es una lista con una longitud N y A es una s seguida de un nulo cuerda."

Tomé un poco de cuidado para escribir s(y así b) para que coincidan con cada "cuerda tirante" exactamente de una manera (que es la razón por la que tanto sy etienen que existir, en lugar de agruparlos en un predicado). Esto los hace a ambos completamente reversibles; por lo tanto, bse puede usar para generar todas las "cadenas de llaves" de una longitud determinada, además de probar si una cadena es una cadena de llaves de una longitud determinada (también se puede usar en una tercera vuelta, para calcular la longitud de una llave cadena, pero es casi seguro su modo de operación menos útil). La implementación es recursiva, por ejemplo, para generar una s , el código generará todas las e s posibles que no sean más largas que la longitud requerida de la salida, y agregará todas las s posibless que encajan en el espacio restante para ellos; Como especifiqué la longitud del argumento por adelantado (dentro de b ), el motor de Prolog sabe que no puede generar una salida que sea más larga que la longitud dada, lo que permite que la recursión termine.

Aquí hay un ejemplo del programa en funcionamiento:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

Haskell, 101 94 bytes

¡7 bytes guardados por Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Casi directo, siguiendo la definición, pero con el ""caso movido.

Utilizar:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(El segundo cálculo lleva menos de un segundo en una máquina lenta).

También me gustaría compartir el resultado de otro enfoque que se me ocurrió mientras pensaba en generar funciones. Define una lista b de listas de cadenas que b!!ncontiene todas las cadenas de llaves de longitud n. Del mismo modo, u!!ncontiene todos los átomos de tamaño n-1. Una cosa buena es que el código no usa ningún número. No está completamente jugó golf: uy ipodría ser inline, y ciertamente pierde algunas otras oportunidades de golf. Desafortunadamente, no parece que pueda hacerse más corto que la primera versión, pero se calcula length $ b !! 10aún más rápido.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)

Mathematica, 116 bytes

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Explicación

Characters@"*([)]"

Encuentra los caracteres de la cadena "*([)]", dando el List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Encuentra las tuplas de la lista anterior con longitud n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Función booleana sin nombre para determinar si la tupla está equilibrada:

#/."*"->Nothing

Eliminar todo "*"en la entrada.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Elimine repetidamente todas las ocurrencias consecutivas de "("y ")"o "["y "]"hasta que la entrada no cambie.

... =={}

Compruebe si el resultado es un vacío List.

Select[ ... , ... ]

Encuentra las tuplas que dan Truecuando se aplica la función booleana.

#<>""&/@

Convierta cada uno Listde los caracteres en Strings.

Python 2, 128 bytes

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Atornille expresiones regulares recursivas: ¡estamos usando el analizador sintáctico de Python! Para verificar que, por ejemplo, *(**[])*es una cadena de llaves, hacemos lo siguiente:

1. Haga una cadena como "*", (0,"*","*", [0,0] ,0) ,"*", donde cada segundo carácter de cuatro es un carácter de las cadenas de llaves, y los caracteres restantes son pegamento para hacer de esta una posible expresión de Python.

2. eval eso.

3. Si eso no arroja un error, imprima s[1::4](los caracteres de la cadena de llaves).

Los caracteres de pegamento se seleccionan de modo que la cadena que hago sea una expresión de Python válida si y solo si cada segundo carácter de cuatro produce una cadena de llaves válida.

PHP, 149 bytes

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Utiliza el método antiguo generar todo lo posible y luego filtrar. Usar como:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4

Python, 134 bytes

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Función sin nombre que devuelve una lista de cadenas válidas de longitud n.
Forma todas las ntuplas de longitud de los caracteres *()[], las une en cadenas usando map(''.join,...)filtros para aquellos que tienen corchetes equilibrados eliminando los "pares" "*"y "()", "[]"a su vez n, comprueba que el resultado es una cadena vacía (el ntiempo es excesivo, especialmente para "*"pero es golfista)

Retina , 78 bytes

El recuento de bytes asume la codificación ISO 8859-1.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

Pruébalo en línea!

Explicación

Estoy generando todas las cadenas posibles de longitud 5 y luego filtro las inválidas.

.+
$*

Esto convierte la entrada a unario, utilizando 1como dígito.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

Esto repetidamente ( +) reemplaza al primero (1 ) uno en cada línea ( %) de tal manera que haga cinco copias de la línea, una para cada carácter posible. Esto se hace usando las sustituciones de prefijos y sufijos, $`y $'para construir el resto de cada línea.

Este ciclo se detiene cuando no hay más 1s para reemplazar. En este punto tenemos todas las cadenas posibles de longitudN , una en cada línea.

%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

Estas dos etapas se ejecutan para cada línea por separado ( %). La primera etapa simplemente duplica la línea, con una ;para separar las dos copias.

La segunda etapa es otro bucle ( +), que elimina repetidamente [], ()o *de la primera copia de la cadena, o elimina un punto y coma al comienzo de la línea (que solo es posible después de que la cadena haya desaparecido por completo).

A`;

Las cadenas válidas son aquellas que ya no tienen un punto y coma delante de ellas, por lo que simplemente descartamos todas las líneas ( A) que contienen un punto y coma.

Python 3.5, 146 bytes

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

Muy largo en comparación con otras respuestas, pero la más corta que pude encontrar actualmente. Tiene la forma de una función lambda anónima y, por lo tanto, debe llamarse en el formato

print(<Function Name>(<Integer>))

Emite un conjunto de Python de desordenados cadenas representan todas las posibles cadenas de llaves de la longitud de entrada.

Por ejemplo, suponiendo que se nombra la función anterior G, la invocación G(3)daría como resultado la siguiente salida:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

¡Pruébelo en línea! (Ideona)

Sin embargo, si, como yo, no eres realmente un fanático de simplificar las cosas usando las funciones integradas, entonces aquí está mi propia respuesta original que no usa ninguna biblioteca externa para encontrar permutaciones, y actualmente está en la friolera de 288 237 bytes :

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

Nuevamente, como la respuesta competitiva, esta tiene la forma de una función lambda y, por lo tanto, también debe llamarse en el formato

print(<Function Name>(<Integer>))

Y genera una lista de Python de cadenas sin clasificar que representan todas las cadenas de llaves de la longitud de entrada. Por ejemplo, si se invocara la lambda como G(3), esta vez la salida sería la siguiente:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Además, este también es mucho más rápido que mi otra respuesta, pudiendo encontrar todos los corsés de longitud 11en aproximadamente 115 segundos , los de longitud 10en aproximadamente 19 segundos , los de longitud 9en aproximadamente 4 segundos y los de longitud 8en aproximadamente 0,73 segundos en mi máquina, mientras que mi respuesta competitiva tarda mucho más de 115 segundos para una entrada de 6.

¡Pruébelo en línea! (Ideona)

05AB1E, 23 bytes

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Algunas de estas características podrían haberse implementado después de que se publicó la pregunta. Cualquier sugerencia es bienvenida!

Pruébalo en línea!

¿Cómo?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string