如何选择子集来形成组合矩阵

Question

我创建了（在学习 VBA 几个月后，然后切换到 Python）一个脚本，该脚本将回溯并选择数字 n 的组合，其顺序相当于更高选择 k 的 n 组合的顺序.

或者换句话说：我通过执行 5C4 创建了 5 个超级组的矩阵。我通过执行 5C2 创建了包含 10 个子集的列表。然后我使用回溯来选择每个子集以形成超集。

使用 [A, B, C, D, E] 的示例：

5C4 = 5 个超集 -> [ABCD, ABCE, 阿布德, ACDE, BCDE]

同样，5C2 = 10 个子集 -> [AB, 交流电， 广告， AE, 公元前， BD, 是， 光盘， 行政长官， 德]

最后，5（子集）* 2（组）= 10（超集）结果如下：

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

• 当然，根据 5C2 列表的顺序，可能会出现一些不同的矩阵解决方案。但是我花了太多时间来找出正确/一般的方法，这似乎是不必要的信息。我还陷入了困境，确保我可以以

  result[row][col][element]

  的每个元素在 col 中出现特定次数的方式排列子集。在我找到一种更快的选择子集的方法之后，我将重新排序它们来执行此操作（如果有人知道如何执行此操作，则作为奖励；我正在考虑排列）。你知道吗，你可以从帕斯卡三角形中得到每个元素的出现次数……但我离题了。

回溯适用于较小的数字，但如果我做更大的事情，比如说

17C15(superset) = 17C3(subset)*5(groups)

，代码运行时间太长（+40h后停止）。

在这些例子中，我认为这应该有效的逻辑是：

5C2 = 10
5C4 =  5
5C4 * 2(groups) = 10

17C3  = 680
17C15 = 136
17C15 * 5(groups) = 680

1.) 我的逻辑正确吗？我认为在选择

n

时，

k_1 < (n/2), k_2 > (n/2), and k_1|k_2 (k_2 is a multiple of k_1)

。

2.）如果这是选择子集最实用的方法，那么任何人都可以帮助优化我的代码吗？

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):
    # check if combo(subset) is a subset of cluster's row
    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):
            # check if used already
            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

成功标准是在最终矩阵、网格中使用所有 680 个组合一次（不重复）。

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

Answer 1

对于查找矩阵的一般情况，给出空间 S 中每个可能组合的列的笛卡尔积选择 k 个元素 e:

令column_height = S - k + 1； 令宽度 = k；

为每个 e 指定一个序数。如果从资源角度来看元素 e 的预期频率很重要，请按频率升序排列序数。

以这种方式填充矩阵：

• 第一列包含元素[1到column_height]
• 第二列元素[2到column_height+1]
• 等等

为了找到任意组合集的映射，k:

• 向下迭代每一列，直到找到 e，k 的成员。
• 存储行并从 k 中删除 e
• 重复直到最后一列，此时 k 将为空，并且您将获得包含 k 成员的行的整数序列。
• 如果这些操作会频繁执行，请考虑缓存 地图。

如果您想要这个的 Java 实现，我可以给您发送一个。

会