如何在 Python 中生成一组 n 个对象的所有唯一嵌套二元组（嵌套配对）？

Question

嵌套二元组，我的意思是这样的： ((a,b),(c,(d,e))) 所有元组都有两个元素。我不需要元素的不同排序，只需要用不同的方式将它们括起来。对于 items = [a, b, c, d]，有 5 个独特的配对，分别是：

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

在一个完美的世界中，我还想控制返回元组的最大深度，这样如果我生成 items = [a, b, c, d] 和 max_depth=2 的所有配对，它只会返回 ((a,b),(c,d)).

出现这个问题是因为我想找到一种方法来生成非交换非结合数的加法结果。如果 a+b 不等于 b+a，并且 a+(b+c) 不等于 (a+b)+c，那么 a、b 和 c 所有可能的和是多少？

我做了一个生成所有配对的函数，但它也返回重复项。

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

例如，它为 ((a,b),(c,d)) 返回 items=[a, b, c, d] 两次，因为它在一种情况下首先配对 (a,b)，而在第二种情况下它首先配对 (c,d)。

对于更多的项目，返回重复项成为一个越来越大的问题。根据 Catalan Numbers (https://oeis.org/A000108)，有重复项，配对的数量呈阶乘增长，没有重复项，则呈指数增长。

n	重复：（n-1）！	没有重复：(2(n-1))!/(n!(n-1)!)
1	1	1
2	1	1
3	2	2
4	6	5
5	24	14
6	120	42
7	720	132
8	5040	429
9	40320	1430
10	362880	4862

正因为如此，我一直在努力想出一种算法，不需要搜索all可能性，只搜索唯一的。同样，控制最大深度也很好，但这可能会添加到现有算法中。到目前为止，我一直未能成功提出一种方法，而且我也没有找到任何资源来解决这个特定问题。我将不胜感激任何帮助或有用资源的链接。

Answer 1

使用递归生成器：

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

输出：

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

唯一性检查：

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

项目倒序：

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 b in split(l[i:]):
            for a 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')))]