如何用Python从两个列表生成所有K长度的无重复配对集合？

给定两个长度分别为N和M的索引列表i1 = list(range(N))、i2 = list(range(M))，需要生成所有长度为K的配对集合，要求每个集合内的配对满足：

• 每个配对由i1和i2各取一个元素组成
• i1中的元素在单个集合内不重复出现
• i2中的元素在单个集合内不重复出现
• K可以小于min(N,M)

解决方案 #

核心思路分三步构造：

1. 从i1中选取K个不重复元素的所有组合
2. 从i2中选取K个不重复元素的所有组合
3. 对每一组选中的i1、i2元素，生成所有可能的一一配对方式（即对i2的K个元素做全排列，再与i1的元素一一对应）

利用Python的itertools模块可高效实现该逻辑，代码如下：

import itertools

def generate_k_pairs(i1, i2, K):
    max_possible = min(len(i1), len(i2))
    if K > max_possible:
        raise ValueError(f"K不能超过两个列表的最小长度{max_possible}")
    
    # 遍历i1的K元素组合和i2的K元素组合
    for selected_i1 in itertools.combinations(i1, K):
        for selected_i2 in itertools.combinations(i2, K):
            # 对选中的i2元素做全排列，生成所有配对方式
            for permuted_i2 in itertools.permutations(selected_i2):
                # 打包成配对列表，也可转成集合（若不关心配对顺序）
                yield list(zip(selected_i1, permuted_i2))

示例测试 #

以N=3、M=4、K=2为例：

i1 = list(range(3))  # [0,1,2]
i2 = list(range(4))  # [0,1,2,3]
K = 2

for pair_set in generate_k_pairs(i1, i2, K):
    print(pair_set)

输出的部分结果如下：

[(0, 0), (1, 1)]
[(0, 1), (1, 0)]
[(0, 0), (1, 2)]
[(0, 2), (1, 0)]
...

每个输出的列表都是符合要求的配对集合：i1元素无重复、i2元素无重复，长度为K=2。

补充说明 #

• 若需将配对集合视为无序（如[(0,0), (1,1)]与[(1,1), (0,0)]视为同一集合），可将生成的列表转成集合：yield set(zip(selected_i1, permuted_i2))
• 该方法时间复杂度为O(C(N,K)*C(M,K)*K!)（C为组合数），对于K较小的场景（如光谱峰匹配），效率可接受
• 当K等于min(N,M)时，该方法等价于生成两个列表间的所有双射配对，兼容已有方案

内容的提问来源于stack exchange，提问作者Ben Farmer