如何选择子集构建组合矩阵？逻辑验证与代码优化求助

我学完VBA后转用Python开发了一款回溯脚本，可按等价于高选择数k的n组合顺序选择n的组合，核心逻辑为：通过组合数运算生成超集矩阵与子集列表，再用回溯法选择子集构建超集。

示例说明 #

以集合[A,B,C,D,E]为例：

• 5C4生成5个超集：[ABCD, ABCE, ABDE, ACDE, BCDE]
• 5C2生成10个子集：[AB, AC, AD, AE, BC, BD, BE, CD, CE, DE]
  最终得到5×2的匹配矩阵：

[[(A, B), (C, D)], [(A, C), (D, E)], [(A, D), (B, E)], [(A, E), (B, C)], [(B, D), (C, E)]]

现有问题 #

回溯法在小数据场景可行，但处理17C15(超集)=17C3(子集)*5(组数)这类大数据时，代码运行超40小时仍未完成。

逻辑依据 #

• 5C2=10，5C4=5，满足5C4×2(组数)=10
• 17C3=680，17C15=136，满足17C15×5(组数)=680

核心疑问 #

1. 我的逻辑是否正确？适用条件为选择n时，k1 < n/2，k2 > n/2，且k1|k2（k2是k1的倍数）。
2. 若此方法为最优子集选择方式，能否优化我的Python代码？

当前代码 #

from itertools import combinations, chain

families = range(1, 6)
choose = 2
groups = 2
size = int(choose*groups)
teams = list(combinations(families, choose))
cluster = list(combinations(families, size)) 
team_len = int(len(teams)/groups) 
zero_set = [(0) for _ in range(choose)]

def check(grid, row, column, subset):
    # 检查子集是否属于对应行的超集
    if ((set(subset) & set(cluster[row])) != set(subset)):
        return False
    check = set(x for x in chain(*grid[row]))
    if(set(tuple(x) for x in grid[row]).intersection(set(subset))):
        return False
    if(check.intersection(set(subset))):
        return False
    # 检查子集是否已被使用
    for x in range(team_len):
        for y in range(groups):
            if (grid[x][y] == subset):
                return False
    return True

def solve(grid, row, column):
    if(row == team_len and column == groups - 1): return True
    if(row == team_len):  
        column += 1
        row = 0

    if grid[row][column] > zero_set:
        return solve(grid, row, column + 1)
    
    for subset in teams:
        if check(grid, row, column, subset):
            grid[row][column] = subset
            if solve(grid, row + 1, column):
                return True
        grid[row][column] = zero_set
    return False

grid = [[zero_set]*groups for _ in range(team_len)]
if solve(grid, 0, 0):
    print("success")
for x in grid:
    print(x)

print("finished")

运行结果 #

success
[(1, 2), (3, 4)]
[(1, 3), (2, 5)]
[(1, 5), (2, 4)]
[(1, 4), (3, 5)]
[(2, 3), (4, 5)]
finished

目标测试参数 #

families = range(1, 18)
choose = 3
groups = 5

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