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

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-1)个加泰罗尼亚数字.但是,如何准确地生成所有结果分组？

谢谢

(顺便说一句:这个问题有超过160个等效公式,都是基于加泰罗尼亚数字列举的不同组合对象.有关这些问题的最新列表,请参阅Richard Stanley的加泰罗尼亚语附录.)

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

Answer 2

实际上有4个元素的超过5个括号; 你实际上并不是指"括号".你真正要问的是N个元素的不同方式的数量reduced,或者你可以用N个元素制作的树的数量,同时仍然保持它们的顺序.

这相当于将表达式精确地细分N-1次.例如,在维基百科的http://en.wikipedia.org/wiki/Catalan_number文章的图中,如果我们有4个元素,那么有五种方法可以将二元运算符应用于它(需要正好有3个应用程序,因此,正好有3个节点):

例如, ((a*b)*c)*d, (a*(b*c))*d, (a*b)*(c*d), a*((b*c)*d), a*(b*(c*d))

这里有一些简洁的python代码:

def associations(seq, **kw):
    """
        >>> associations([1,2,3,4])
        [(1, (2, (3, 4))), (1, ((2, 3), 4)), ((1, 2), (3, 4)), ((1, (2, 3)), 4), (((1, 2), 3), 4)] 
    """
    grouper = kw.get('grouper', lambda a,b:(a,b))
    lifter = kw.get('lifter', lambda x:x)

    if len(seq)==1:
        yield lifter(seq[0])
    else:
        for i in range(len(seq)):
            left,right = seq[:i],seq[i:] # split sequence on index i

            # return cartesian product of left x right
            for l in associations(left,**kw):
                for r in associations(right,**kw):
                    yield grouper(l,r)

请注意如何grouper使用此代码替换有趣的函数,例如grouper=list,或grouper=Tree,或grouper=....

演示:

for assoc in associations('abcd'):
    print assoc

('a', ('b', ('c', 'd')))
('a', (('b', 'c'), 'd'))
(('a', 'b'), ('c', 'd'))
(('a', ('b', 'c')), 'd')
((('a', 'b'), 'c'), 'd')

Answer 3

使用递归

   for each balanced expression of n-1 parentheses 
     for each pos i from 0 to m of an expression
       add '('
       for each pos  j from i + 1 to m
          add ')' if expression is balanced

您将收到的订单如下：

n=0: 

n=1: ()

n=2: []() , [()]

n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}

在这里，我每次都会更改括号(,[,{以突出显示算法的工作原理。