如何在 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))两次 for ，因为它在一种情况下将第一个配对，在第二种情况下将第一个items=[a, b, c, d]配对。(a,b)(c,d)

对于大量项目来说，返回重复项成为一个越来越大的问题。根据加泰罗尼亚数字 ( 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

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

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

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

Answer 2

该算法完全归功于 mozway - 我最初的想法是用反向抛光表示法表示配对，这不会有助于以下优化：

首先，我们替换两个嵌套循环：

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

-with itertools.product，它本身会缓存内部调用的结果split(...)，并在内部 C 代码中生成配对，这会运行得更快。

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

接下来，我们缓存之前调用的结果split(...)。为此，我们必须牺牲生成器的惰性，并确保我们的函数参数是可哈希的。明确地说，这意味着创建一个包装器，将输入列表转换为元组，并修改函数体以返回列表而不是生成。

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

然后我们用functools.cache装饰该函数，以执行缓存。所以把它们放在一起：

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

测试以下输入 -

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

- 产生以下时序：

Original: 5.922573089599609
Revised: 0.08888077735900879

我还验证了结果是否与原始顺序完全匹配。

再次，完全归功于 mozway 的算法。我刚刚应用了一些优化来加快速度。