Python 如何得到一个表达式所有可能的括号组合？

Question

给定一个包含多个元素的列表，找出所有可能的括号组合。例如 [1, 2, 3, 4]，它将 return

[
[1,2,3,4],
[[1,2],3,4],
[[1,2],[3,4]],
[1,[2,3],4],
[1,2,[3,4]],
[[1,2,3],4],
[[[1,2],3],4],
[[1,[2,3]],4],
[1,[2,3,4]],
[1,[[2,3],4]],
[1,[2,[3,4]]]
]

排名不分先后。

请阅读： 在您将其标记为 How to print all possible balanced parentheses for an expression? 的副本之前，虽然相似，但这是一个略有不同的问题。在那个问题中，它只要求包含每个值的括号表达式。然而，这个问题要求每一个组合，不管每个元素是否在括号内。

Answer 1

列出列表中所有可能的树：

从根开始迭代所有可能的children个数；
对于选定数量的 children，迭代所有可能的方式将列表拆分为该数量的子列表；
递归查找子列表所有可能的子树；
使用itertools.product合并children的所有可能子树。

from itertools import product, combinations, pairwise, chain

def all_trees(seq):
    if len(seq) <= 1:
        yield from seq
    else:
        for n_children in range(2, len(seq)+1):
            for breakpoints in combinations(range(1, len(seq)), n_children-1):
                children = [seq[i:j] for i,j in pairwise(chain((0,), breakpoints, (len(seq)+1,)))]
                yield from product(*(all_trees(child) for child in children))

测试：

for seq in ([], [1], [1,2], [1,2,3], [1,2,3,4]):
    print(seq)
    print(list(all_trees(seq)))
    print()

[]
[]

[1]
[1]

[1, 2]
[(1, 2)]

[1, 2, 3]
[(1, (2, 3)), ((1, 2), 3), (1, 2, 3)]

[1, 2, 3, 4]
[(1, (2, (3, 4))), (1, ((2, 3), 4)), (1, (2, 3, 4)), ((1, 2), (3, 4)), ((1, (2, 3)), 4), (((1, 2), 3), 4), ((1, 2, 3), 4), (1, 2, (3, 4)), (1, (2, 3), 4), ((1, 2), 3, 4), (1, 2, 3, 4)]

Python 如何得到一个表达式所有可能的括号组合？

How to get all possible parentheses combinations for an expression with Python?

python

recursion

combinatorics

catalan