如何使用Python获取表达式的所有可能的括号组合？

Question

给定一个包含多个元素的列表，找到所有可能的括号组合。例如[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]]]
]

没有特定的顺序。

请阅读：在将其标记为如何打印表达式的所有可能的平衡括号的副本之前？，虽然相似，但这是一个略有不同的问题。在该问题中，它只要求括号表达式，其中每个值都被包围。然而，这个问题要求每一个组合，无论每个元素是否在括号内。

Answer 1

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

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

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)]