algorithm - 如何打印表达式所有可能的平衡括号？

Question

例如，对于元素 a,b,c,d，有 5 种可能的方法来获取相邻元素并将它们缩减为单个元素，其中必须同时合并两个元素(以下用括号表示):

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

第一个示例乘以 a*b，然后乘以 c，然后乘以 d。第二个示例首先乘以 b*c，然后将该乘积乘以 a，然后将该乘积乘以 d。

任何包含 2n 个元素的有效圆括号表达式都必然有 n 个 ( 和 n )，其属性是，从左到右阅读，总是至少有同样多的元素(作为)。

我知道对于n个数，路数是第(n-1)个Catalan number .但是如何准确地生成所有结果分组？

谢谢

(顺便说一句:这个问题有超过 160 个等价公式，全部基于加泰罗尼亚数字列举的不同组合对象。有关这些的最新列表，请参阅 Richard Stanley's Catalan Addendum。)

Answer 1

这是 Python 中的实际代码，使用生成器来避免使用过多内存。

#! /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