How can I generate all unique nested 2-tuples (nested pairings) of a set of n objects in Python?

By nested 2-tuples, I mean something like this: ((a,b),(c,(d,e))) where all tuples have two elements. I don't need different orderings of the elements, just the different ways of putting parentheses around them. For items = [a, b, c, d], there are 5 unique pairings, which are:

(((a,b),c),d)  
((a,(b,c)),d)  
(a,((b,c),d))  
(a,(b,(c,d)))  
((a,b),(c,d))

In a perfect world I'd also like to have control over the maximum depth of the returned tuples, so that if I generated all pairings of items = [a, b, c, d] with max_depth=2, it would only return ((a,b),(c,d)).

This problem turned up because I wanted to find a way to generate the results of addition on non-commutative, non-associative numbers. If a+b doesn't equal b+a, and a+(b+c) doesn't equal (a+b)+c, what are all the possible sums of a, b, and c?

I have made a function that generates all pairings, but it also returns duplicates.

import itertools

def all_pairings(items):
    if len(items) == 2:
        yield (*items,)
    else:
        for i, pair in enumerate(itertools.pairwise(items)):
            for pairing in all_pairings(items[:i] + [pair] + items[i+2:]):
                yield pairing

For example, it returns ((a,b),(c,d)) twice for items=[a, b, c, d], since it pairs up (a,b) first in one case and (c,d) first in the second case.

Returning duplicates becomes a bigger and bigger problem for larger numbers of items. With duplicates, the number of pairings grows factorially, and without duplicates it grows exponentially, according to the Catalan Numbers (https://oeis.org/A000108).

Because of this, I have been trying to come up with an algorithm that doesn't need to search through all the possibilities, only the unique ones. Again, it would also be nice to have control over the maximum depth, but that could probably be added to an existing algorithm. So far I've been unsuccessful in coming up with an approach, and I also haven't found any resources that cover this specific problem. I'd appreciate any help or links to helpful resources.

Using a recursive generator:

items = ['a', 'b', 'c', 'd']

def split(l):
    if len(l) == 1:
        yield l[0]
    for i in range(1, len(l)):
        for a in split(l[:i]):
            for b in split(l[i:]):
                yield (a, b)
        
list(split(items))

Output:

[('a', ('b', ('c', 'd'))),
 ('a', (('b', 'c'), 'd')),
 (('a', 'b'), ('c', 'd')),
 (('a', ('b', 'c')), 'd'),
 ((('a', 'b'), 'c'), 'd')]

Check of uniqueness:

assert len(list(split(list(range(10))))) == 4862

Reversed order of the items:

items = ['a', 'b', 'c', 'd']

def split(l):
    if len(l) == 1:
        yield l[0]
    for i in range(len(l)-1, 0, -1):
        for a in split(l[:i]):
            for b in split(l[i:]):
                yield (a, b)
        
list(split(items))

[((('a', 'b'), 'c'), 'd'),
 (('a', ('b', 'c')), 'd'),
 (('a', 'b'), ('c', 'd')),
 ('a', (('b', 'c'), 'd')),
 ('a', ('b', ('c', 'd')))]

With maxdepth:

items = ['a', 'b', 'c', 'd']

def split(l, maxdepth=None):
    if len(l) == 1:
        yield l[0]
    elif maxdepth is not None and maxdepth <= 0:
        yield tuple(l)
    else:
        for i in range(1, len(l)):
            for a in split(l[:i], maxdepth=maxdepth and maxdepth-1):
                for b in split(l[i:], maxdepth=maxdepth and maxdepth-1):
                    yield (a, b)

list(split(items))
# or
list(split(items, maxdepth=3))
# or
list(split(items, maxdepth=2))

[('a', ('b', ('c', 'd'))),
 ('a', (('b', 'c'), 'd')),
 (('a', 'b'), ('c', 'd')),
 (('a', ('b', 'c')), 'd'),
 ((('a', 'b'), 'c'), 'd')]

list(split(items, maxdepth=1))

[('a', ('b', 'c', 'd')),
 (('a', 'b'), ('c', 'd')),
 (('a', 'b', 'c'), 'd')]

list(split(items, maxdepth=0))

[('a', 'b', 'c', 'd')]

Full-credit to mozway for the algorithm - my original idea was to represent the pairing in reverse-polish notation, which would not have lent itself to the following optimizations:

First, we replace the two nested loops:

for a in split(l[:i]):
    for b in split(l[i:]):
        yield (a, b)

-with itertools.product, which will itself cache the results of the inner split(...) call, as well as produce the pairing in internal C code, which will run much faster.

yield from product(split(l[:i]), split(l[i:]))

Next, we cache the results of the previous split(...) calls. To do this we must sacrifice the laziness of generators, as well as ensure that our function parameters are hashable. Explicitly, this means creating a wrapper that casts the input list to a tuple, and to modify the function body to return lists instead of yielding.

def split(l):
    return _split(tuple(l))

def _split(l):
    if len(l) == 1:
        return l[:1]
    
    res = []
    for i in range(1, len(l)):
        res.extend(product(_split(l[:i]), _split(l[i:])))
    return res

We then decorate the function with functools.cache, to perform the caching. So putting it all together:

from itertools import product
from functools import cache

def split(l):
    return _split(tuple(l))

@cache
def _split(l):
    if len(l) == 1:
        return l[:1]
    
    res = []
    for i in range(1, len(l)):
        res.extend(product(_split(l[:i]), _split(l[i:])))
    return res

Testing for following input-

test = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']`

-produces the following timings:

Original: 5.922573089599609
Revised: 0.08888077735900879

I did also verify that the results matched the original exactly- order and all.

Again, full credit to mozway for the algorithm. I've just applied a few optimizations to speed it up a bit.