Python中从列表生成所有互不重叠配对集合的最快实现方案

实现逻辑 #

这类问题最优时间复杂度为O(n!!)（n为列表长度，仅n为偶数时有合法输出），可以用递归思路快速实现：

• 每次取当前待拆分列表的第一个元素，和剩余所有元素逐一配对
• 每完成一次配对后，将两个已配对元素从待拆分列表中移除，递归处理剩余元素
• 待拆分列表为空时，返回当前生成的配对集合即可

Python 示例代码 #

def get_all_pairings(lst):
    if not lst:
        yield []
        return
    first = lst[0]
    for i in range(1, len(lst)):
        pair = (first, lst[i])
        for rest in get_all_pairings(lst[1:i] + lst[i+1:]):
            yield [pair] + rest

# 测试示例
test_lst = ['A', 'B', 'C', 'D']
for idx, pairing in enumerate(get_all_pairings(test_lst), 1):
    print(f"{idx}. {{{','.join([f'[{p[0]},{p[1]}]' for p in pairing])}}}")

输出结果 #

运行代码后会得到你需要的结果：

1. {[A,B],[C,D]}
2. {[A,C],[B,D]}
3. {[A,D],[B,C]}

内容的提问来源于stack exchange，提问作者Shreya Joshi