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.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]
3
The number of entries in the output is A025235
– Gabriel Benamy – 2016-11-30T03:48:52.257@GabrielBenamy Ah. I was wondering whether that had been looked at before. Interesting. – Esolanging Fruit – 2016-11-30T05:57:48.220
2What is the winning condition? I assume shortest program (code golf). – Zgarb – 2016-11-30T07:46:07.963
Related. – Martin Ender – 2016-11-30T07:59:46.053
1Since everyone is assuming this is code golf, I will tag the challenge accordingly (as it would otherwise make all existing answers somewhat pointless). If you intended a different winning criterion, you could consider posting a new challenge. – Martin Ender – 2016-11-30T09:04:53.083
A longer test case? – edc65 – 2016-11-30T10:57:02.200
@edc65 5, 6, and 7 have lengths 61, 191, and 603 respectively. Are more test cases really needed? – Esolanging Fruit – 2016-12-01T05:29:26.167
I can find all the lengths at A02535. What I need is the string list. Luckily there are many valid answers now that give the correct list. – edc65 – 2016-12-01T07:25:40.620
The point is mainly that I'm too lazy to write them out :-) – Esolanging Fruit – 2016-12-01T21:32:15.343