algorithm - How to print all possible balanced parentheses for an expression?

Question

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses):

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

The first example multiplies a*b, then multiplies that product by c, then multiplies that product by d. The second example first multiplies b*c, then multiplies that product by a, then multiplies that product by d.

Any valid parenthesized expression of 2n elements will necessarily have n ( and n ) with the property that, reading from left to right, there are always at least as many ( as ).

I know that for n numbers, the number of ways is the (n-1)th Catalan number. But how does one accurately generate all the resulting groupings?

Thanks

(As an aside: There are over 160 equivalent formulations of this problem, all based on different combinatorial objects enumerated by the Catalan Numbers. For the most up to date list of these, see Richard Stanley's Catalan Addendum.)

Answer 1

Here is actual code in Python, using generators to avoid using too much memory.

#! /usr/bin/python

def parenthesized (exprs):
    if len(exprs) == 1:
        yield exprs[0]
    else:
        first_exprs = []
        last_exprs = list(exprs)
        while 1 < len(last_exprs):
            first_exprs.append(last_exprs.pop(0))
            for x in parenthesized(first_exprs):
                if 1 < len(first_exprs):
                    x = '(%s)' % x
                for y in parenthesized(last_exprs):
                    if 1 < len(last_exprs):
                        y = '(%s)' % y
                    yield '%s%s' % (x, y)

for x in parenthesized(['a', 'b', 'c', 'd']):
    print x