基于Numpy矩阵的互斥与子集关系生成合法结果的实现问题

问题背景 #

假设某事件包含多个可共存结果（比如A与B的网球发球局，存在「A获胜」「B获胜」「A得分」等结果），部分结果存在以下关系：

• 互斥关系：用Numpy矩阵D表示，D[i][j] = 1意味着事件i和j不能同时发生
• 子集关系：用Numpy矩阵S表示，S[i][j] = 1意味着事件i是事件j的子集（即若i发生，j必须同时发生）

目标是实现函数，输入D和S，输出所有符合规则的合法结果矩阵X（X为二进制矩阵，每行代表一个合法的事件组合，1表示对应事件发生）。原代码的子集过滤逻辑存在错误，会生成违反子集规则的非法组合，需要修正。

错误原因分析 #

常见的子集过滤错误包括：

1. 搞反了子集关系的方向（比如误判为j是i的子集）
2. 未遍历所有子集关系对，遗漏部分校验
3. 校验逻辑错误（比如允许i发生但j不发生的情况）

修正后的代码实现 #

import numpy as np

def generate_valid_X(D, S):
    num_events = D.shape[0]
    # 生成所有可能的二进制事件组合（共2^num_events种）
    all_combinations = np.array([np.binary_repr(i, width=num_events) for i in range(2**num_events)], dtype='U')
    all_combinations = all_combinations.view('U1').astype(int)
    
    # 第一步：过滤违反互斥规则的组合
    mask_disjoint = np.ones(all_combinations.shape[0], dtype=bool)
    for i in range(num_events):
        for j in range(i + 1, num_events):
            if D[i][j] == 1:
                # 排除同时选中i和j的组合
                invalid = (all_combinations[:, i] == 1) & (all_combinations[:, j] == 1)
                mask_disjoint &= ~invalid
    
    valid_after_disjoint = all_combinations[mask_disjoint]
    
    # 第二步：过滤违反子集规则的组合
    mask_subset = np.ones(valid_after_disjoint.shape[0], dtype=bool)
    for i in range(num_events):
        for j in range(num_events):
            if S[i][j] == 1:
                # 排除「i发生但j不发生」的非法组合
                invalid = (valid_after_disjoint[:, i] == 1) & (valid_after_disjoint[:, j] == 0)
                mask_subset &= ~invalid
    
    return valid_after_disjoint[mask_subset]

代码说明 #

1. 生成所有组合：通过二进制遍历生成所有可能的事件发生状态，转换为Numpy矩阵方便批量处理
2. 互斥规则过滤：遍历所有互斥事件对，直接排除同时选中两个互斥事件的组合
3. 子集规则过滤：遍历所有子集关系对，严格校验「子集事件发生则父事件必须发生」的规则，排除非法组合

示例验证 #

以网球发球局为例：

• 事件0：A获胜
• 事件1：B获胜
• 事件2：A得分（A得分是A获胜的子集）

定义矩阵：

# 互斥矩阵：A获胜和B获胜互斥
D = np.array([
    [0, 1, 0],
    [1, 0, 0],
    [0, 0, 0]
])

# 子集矩阵：A得分是A获胜的子集
S = np.array([
    [0, 0, 0],
    [0, 0, 0],
    [1, 0, 0]
])

调用函数后得到的合法结果：

valid_X = generate_valid_X(D, S)
print(valid_X)

输出：

[[0 0 0]
 [1 0 0]
 [1 0 1]
 [0 1 0]]

所有结果均符合规则：

• [0,0,0]：无事件发生（如发球失误）
• [1,0,0]：A获胜（未记录得分）
• [1,0,1]：A获胜且A得分（符合子集规则）
• [0,1,0]：B获胜

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