如何获得与Python表达式表达的所有可能的括号组合？

发布于 2025-01-25 20:54:27 字数 446 浏览 0 评论 0原文

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

以任何层次顺序返回。

请阅读：在将其标记为如何为表达式打印所有可能的平衡括号？，尽管相似，但这与此相似。在这个问题中，它只要求括号表达每个值都被包围。但是，无论每个元素是否在括号内，这个问题都要求每个组合。

原文

Given a list of several elements, find all the possible parentheses combinations. For example with [1, 2, 3, 4], it would 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]]]
]

in no paticular order.

PLEASE READ: Before you mark this as a duplicate of How to print all possible balanced parentheses for an expression?, although similar, it is a slightly different question than that. In that question, it only asks for parentheses expressions where every value is surrounded. This question however asks for every single combination regardless of whether every element is within parentheses.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

人疚 2025-02-01 20:54:27

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

从根部迭代所有可能的孩子数量；
对于选定的儿童，可以迭代所有可能的方法，将清单分为该数量的人数；
递归地找到了冠军的所有可能的子树；
使用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)]

To list all the possible trees from the list:

Iterate on all the possible number of children from the root;
For a chosen number of children, iterate on all the possible ways to split the list into that number of sublists;
Recursively find all the possible subtrees of the sublists;
Combine all the possible subtrees of the children using 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))

Testing:

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

回复收藏 0 原文

~没有更多了~