How is Schroeder's generalized parentheses sequence (A001003) actually used to generated parentheses expressions?

Question

The sequence A001003 counts the "number of ways to insert parentheses in a string of n+1 symbols". What I'm trying to figure out is how to generate the expressions with parentheses (in code). For example, I want to generate the following for n=4 (from this question):

abcd, (ab)cd, a(bc)d, ab(cd), (ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, and ((ab)c)d

I thought perhaps I could list brackets as a simple left-to-right "stack" of sorts:

n=3
0, 0, 0
1,-1, 0
0, 1,-1

n=4
0, 0, 0, 0
0, 0, 1,-1
0, 1,-1, 0
1,-1, 0, 0
1,-1, 1,-1
0, 1, 0,-1
0, 2,-1,-1
0, 1, 1,-2
1, 0,-1, 0
2,-1,-1, 0
1, 1,-2, 0

But this has turned out rather complicated to implement. Right now I'm brute-force generating expressions, throwing out mal-formed expressions, and checking for duplicates. I'm not looking for an actual code solution, just someone to point me in the right direction or maybe a related sequence on OEIS that I have missed. For instance, a listing of all values up to, say, n=8 is all I need. But it would be nice to generate up to arbitrary n.

I have seen this which does not generate the above. As well as wiki and mathworld which don't seem to have the information I want, unless I missed it.

(note to editors: I tagged this with "catalan-numbers" but this question is about "super-Catalan numbers or little Schroeder numbers" to quote A001003 and I'm not sure if that's correct)

Answer 1

Here's Java code that generates these strings in two different ways.

The first version (using the method combine) is simpler but slightly more expensive, since it produces sets of strings at each recursion step and successively combines the strings in these sets. The basic idea is to divide the unparenthesized string into two or more pieces at all possible positions, wrapping all pieces of length $\gt1$ in parentheses and recursively inserting parentheses into them. This version erroneously wraps the entire strings in parentheses, but these can easily be removed.

The second version (using the method recurse) is a bit more complicated but produces one string at a time, which may be favourable both time- and spacewise for larger $n$. It works by maintaining a stack to remember how many symbols or symbol groups have been added so far at each nesting level, so that the requirement that at least $2$ must be added before closing the parentheses can be enforced. The parameter k keeps track of how many symbols are minimally required to fulfil all requirements of the currently open parentheses, to avoid following branches that won't lead to any admissible strings.

Feel free to ask if further explanations are required.