如何在Python中生成n个对象的唯一嵌套二元组并控制最大深度

问题定义 #

这里的嵌套二元组指所有元组均包含两个元素的结构，例如((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时，需要枚举多个元素的所有可能和形式。

当前实现的缺陷 #

我编写了一个生成所有配对的函数，但会返回大量重复项：

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

例如针对items=[a, b, c, d]，((a,b),(c,d))会被返回两次——一次是先配对(a,b)，另一次是先配对(c,d)。

随着元素数量增加，重复问题会急剧恶化：带重复的配对数按(n-1)!阶乘增长，而无重复的唯一配对数符合卡特兰数（OEIS编号A000108），两者的数值对比如下：

寻求帮助 #

我需要一种无需遍历所有可能性、仅生成唯一配对的算法，同时最好支持最大深度控制，但目前尚未找到可行方法或相关资料，希望得到技术方案或思路指导。

内容的提问来源于stack exchange，提问作者Truls Henriksson