求将n*k规模集合拆分为k大小子集的所有组合方案

给定一个元素总数为n×k的集合，需要枚举所有将其划分为n个互不相交的k元子集的可能方案——最终结果是一个集合，其中每个元素都是包含n个k元子集的列表，且所有子集的并集等于原集合，子集间没有重叠元素。

示例 #

原集合：

(1, 2, 3, 4, 5, 6)

拆分参数：n=2，k=3（总元素数6=2×3）
预期输出：

[[(1,2,3),(4,5,6)],
 [(1,2,4),(3,5,6)],
 [(1,2,5),(3,4,6)],
 [(1,2,6),(3,4,5)],
 [(1,3,4),(2,5,6)],
 [(1,3,5),(2,4,6)],
 [(1,3,6),(2,4,5)],
 [(1,4,5),(2,3,6)],
 [(1,4,6),(2,3,5)],
 [(1,5,6),(2,3,4)]]

思路优化与实现 #

你提到的“先找出所有k元子集再分组”的思路可行，但直接执行会产生大量重复计算和无效分组。推荐用递归+固定基准元素剪枝的方式优化，避免重复方案并提升效率：

• 每次从剩余元素中选取包含「剩余元素最小值」的k元子集，确保每个划分方案只被生成一次（比如不会把[(1,2,3),(4,5,6)]和[(4,5,6),(1,2,3)]视为不同方案）
• 递归处理剩余未划分的元素，直到所有元素都被分配完毕

以下是Python实现代码：

from itertools import combinations

def generate_partitions(elements, k):
    # 递归终止条件：所有元素已划分完毕
    if not elements:
        return [[]]
    
    # 固定剩余元素中的第一个元素，避免生成重复划分
    first_element = elements[0]
    # 生成所有包含first_element的k元子集
    partitions = []
    for subset in combinations(elements[1:], k-1):
        current_subset = (first_element,) + subset
        # 计算剩余未划分的元素
        remaining_elements = [x for x in elements if x not in current_subset]
        # 递归处理剩余元素，拼接结果
        for rest_partition in generate_partitions(remaining_elements, k):
            partitions.append([current_subset] + rest_partition)
    
    return partitions

# 测试示例
original_set = (1, 2, 3, 4, 5, 6)
result = generate_partitions(list(original_set), 3)
for partition in result:
    print(partition)

代码说明 #

• 通过固定每次选取的子集包含剩余元素的最小值，从根源上避免了因子集顺序不同导致的重复方案
• 递归过程中仅处理剩余元素，减少了不必要的组合尝试，效率远高于“全量生成k元子集再筛选”的方式

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