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

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.

CodePudding user response：

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