5

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.

miclol
  • 53
  • 5
  • *"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."* I find these two sentences very confusing. I suggest to think a bit more about the precise difference between that question and your question. This will help you find a solution to your problem. – Stef May 04 '22 at 10:22
  • The other question you linked returns all the possible **binary trees**. What you want is to return **all trees**, including trees where the numbers of children are sometimes different that 2. – Stef May 04 '22 at 10:23

1 Answers1

1

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)]
Stef
  • 13,242
  • 2
  • 17
  • 28