Generate all brace-strings of length n

Question

A brace string is defined as a string consisting of the characters *()[] in which braces match correctly:

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

This is a valid brace-string:

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

But these are not:

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

Your task is to write a program (or function) that, given a positive integer n, takes a number as input and outputs (or returns) all valid brace strings of length n.

Specifications

• You may output the strings in any order.
• You may output as a list or a string separated by a different character.
• Your program must handle 0 correctly. There is 1 possible brace-string of length 0, which is the empty string "".
• This is code-golf, so the shortest valid answer – measured in bytes – wins.

Test Cases

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

Answer 1

Prolog, 69 bytes

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

One of the most interesting properties of Prolog is that in many cases it's capable of running a program backwards; for example, instead of testing to see if something's true, you can generate all solutions for which it's true, and instead of checking the length of a string, you can generate all strings with a given length. (Another nice property of Prolog is that it requires whitespace after the end of each predicate definition, and a newline can be inserted as cheaply as a space; thus even golfed programs are often fairly readable.)

The above defines a predicate (the equivalent of a function) b which tests to see if a string has a given length and is a "brace string" as defined in the question. Specifically, it does this via Prolog's grammar/regex/pattern-match support that gives some nice, short sugar for defining this sort of expression (apparently this is standard/portable, but I was unaware of this while originally writing the answer, and thus assumed the answer would work on only one Prolog implementation; it seems it works on every implementation that complies with the standards, though). The program can be translated into English fairly directly; the first two lines say "an s is an empty string, or an e followed by an s; an e is an asterisk, or an s in parentheses, or an s in square brackets". The third line can be interpreted as "The b of N can be A if A is a list with length N and A is an s followed by a null string."

I took some care to write s (and thus b) so that they match each "brace string" in exactly one way (which is the reason that both s and e have to exist, rather than grouping them into one predicate). This makes them both entirely reversible; thus b can be used to generate all "brace strings" of a given length, in addition to testing if a string is a brace string of a given length (it can also be used a third way round, to figure out the length of a brace string, but that is almost certainly its least useful mode of operation). The implementation is recursive, e.g. to generate an s, the code will generate all possible es that are no longer than the required length of the output, and append all possible ss that fit in the remaining space to them; because I specified the length of the argument in advance (within b), the Prolog engine knows that it can't generate output that's longer than the given length, which allows the recursion to terminate.

Here's an example of the program in operation:

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

Answer 2

Haskell, 101 94 bytes

7 bytes saved by 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<-["()","[]"]]

Almost straightforward, following the definition, but with the "" case moved.

Use:

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

(The second computation takes less than a second on a slow machine.)

I'd also like to share the result of another approach I came up with while thinking about generating functions. It defines a list b of lists of strings such that b!!n contains all brace-strings of length n. Similarly, u!!n contains all atoms of size n-1. One nice thing is that the code is not using any numbers. It is not completely golfed: u and i could be inlined, and it certainly misses a few other golfing opportunities. Unfortunately, it doesn't look like it can be made shorter than the first version, but it computes length $ b !! 10 even faster.

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)

Answer 3

Mathematica, 116 bytes

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

Explanation

Characters@"*([)]"

Find the characters of the string "*([)]", giving the List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Find the tuples of the above list with length n.

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

Unnamed Boolean function to find whether the tuple is balanced:

#/."*"->Nothing

Delete all "*" in the input.

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

Repeatedly delete all consecutive occurrences of "(" and ")" or "[" and "]" until the input does not change.

... =={}

Check whether the result is an empty List.

Select[ ... , ... ]

Find the tuples that give True when the Boolean function is applied.

#<>""&/@

Convert each List of characters into Strings.

Answer 4

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

Screw recursive regexes – we’re using Python’s parser! In order to verify that, for example, *(**[])* is a brace-string, we do the following:

1. Make a string like "*", (0,"*","*", [0,0] ,0) ,"*", where every second character of four is a character from the brace-strings, and the remaining characters are glue to make this a potential Python expression.

2. eval it.

3. If that doesn’t throw an error, print s[1::4] (the brace-string characters).

The glue characters are picked so that the string I make is a valid Python expression if and only if taking every second character out of four yields a valid brace-string.

Answer 5

Jelly, 29 bytes

-3 bytes thanks to @JonathanAllan

Please, alert me if there are any problems/bugs/errors or bytes I can knock off!

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

Try it online!

The previous solution(s) I had:

“[(*)]”ṗµḟ”*œṣ⁾()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ị

Explanation (My best attempt at a description):

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

Answer 6

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

Uses the good old generate all possible and then filter method. Use like:

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

Answer 7

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

Unnamed function that returns a list of valid strings of length n.
Forms all length n tuples of the characters *()[], joins them into strings using map(''.join,...) and filters for those that have balanced brackets by removing the "pairs" "*", "()", and "[]" in turn n times and checking that the result is an empty string (n times is overkill, especially for "*" but is golfier).

Answer 8

Retina, 78 bytes

Byte count assumes ISO 8859-1 encoding.

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

A`;

Try it online!

Explanation

I'm generating all possible strings of length 5 and then I filter out the invalid ones.

.+
$*

This converts the input to unary, using 1 as the digit.

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

This repeatedly (+) replaces the first (1) one in each line (%) in such a way that it makes five copies of the line, one for each possible character. This is done by using the prefix and suffix substitutions, $` and $' to construct the remainder of each line.

This loop stops when there are no more 1s to replace. At this point we've got all possible strings of length N, one on each line.

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

These two stages are executed for each line separately (%). The first stage simply duplicates the line, with a ; to separate the two copies.

The second stage is another loop (+), which repeatedly removes [], () or * from the first copy of the string, or removes a semicolon at the beginning of the line (which is only possible after the string has vanished completely).

A`;

Valid strings are those that no longer have a semicolon in front of them, so we simply discard all lines (A) which contain a semicolon.

Answer 9

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

Very long compared to other answers, but the shortest one I could currently find. It is in the form of an anonymous lambda function and therefore must be called in the format

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

Outputs a Python set of unordered strings representing all possible brace-strings of the input length.

For example, assuming the above function is named G, invoking G(3) would result in the following output:

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

Try It Online! (Ideone)

---

However, if, like me, you aren't really a fan of simplifying things using built-ins, then here is my own original answer not using any external libraries to find permutations, and currently standing at a whopping 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)]

Again, like the competing answer, this one is in the form of a lambda function and therefore must also be called in the format

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

And outputs a Python list of unsorted strings representing all brace-strings of the input length. For example, if the lambda were to be invoked as G(3), this time the output would be the following:

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

Also, this one is also a lot faster than my other answer, being able to find all brace-strings of length 11 in about 115 seconds, those of length 10 in about 19 seconds, those of length 9 in about 4 seconds, and those of length 8 in about 0.73 seconds on my machine, whereas my competing answer takes much longer than 115 seconds for an input of 6.

Try It Online! (Ideone)

Answer 10

05AB1E, 23 bytes

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

Some of these features might have been implemented after the question was posted. Any suggestions are welcome!

Try it online!

How?

…[(* - 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