Python实现：从允许列表生成阻断列表的代码修复需求

传入包含实体组的Policy列表，规则是组内实体可互通，组间实体不可互通，需返回无法互通的实体组合列表。示例如下：

• policy1 = [['A'], ['B', 'C'], ['D']]，对应阻断列表为[('A', 'C', 'D'), ('A', 'B', 'D')]
• policy2 = [['A', 'B'], ['B', 'C'], ['D']]，期望阻断列表为[('A', 'C', 'D'), ('B', 'D')]

原代码处理含公共实体的policy2时输出错误，错误输出为[('A', 'C', 'D'), ('A', 'B', 'D'), ('B', 'D'), ('B', 'C', 'D')]，需修复代码或提供更优实现。

原代码 #

from itertools import product

def generate_block_list(policy):
    block_set = set()

    # Generate block list for each entity in the policy
    for entity in policy:
        other_entities = [e for e in policy if e != entity]

        # Generate all possible combinations of the current entity with other entities
        combinations = list(product(entity, *other_entities))
        unique_combinations = [tuple(sorted(set(combination))) for combination in combinations]

        # Add combinations to the block list
        block_set.update(unique_combinations)

    block_list = list(block_set)
    return block_list

# Example usage:
policy1 = [['A'], ['B', 'C'], ['D']]
block_list1 = generate_block_list(policy1)
print("\nPolicy:", policy1)
print("Block List:", block_list1)

policy2 = [['A', 'B'], ['B', 'C'], ['D']]
block_list2 = generate_block_list(policy2)
print("\nPolicy:", policy2)
print("Block List:", block_list2)

policy3 = [['A'], ['B', 'C'], ['D', 'E']]
block_list3 = generate_block_list(policy3)
print("\nPolicy:", policy3)
print("Block List:", block_list3)

policy4 = [['A'], ['B', 'C'], ['D', 'E'], ['F'], ['G']]
block_list4 = generate_block_list(policy4)
print("\nPolicy:", policy4)
print("Block List:", block_list4)

问题根源 #

原代码的核心错误：

1. 直接用e != entity判断其他组，当组存在公共元素（如policy2中的['A','B']和['B','C']）时，会重复处理并生成冗余组合。
2. 未考虑实体的连通关系——若两个实体通过公共元素属于同一连通组（如A、B、C），它们之间不需要被阻断，原代码的组合逻辑会错误生成这类无效阻断项。

正确逻辑应为：先合并所有连通的实体组（通过公共元素），再生成跨所有连通组的元素组合，这些组合才是需要阻断的对象。

修复后的实现方案 #

from itertools import product

def find_connected_groups(policy):
    # 合并重叠/连通的实体组
    connected_groups = []
    for group in policy:
        current = set(group)
        # 找出所有和当前组有交集的已存在连通组
        merged_indices = []
        for idx, cg in enumerate(connected_groups):
            if current & cg:
                current.update(cg)
                merged_indices.append(idx)
        # 移除已合并的旧组
        for idx in reversed(merged_indices):
            del connected_groups[idx]
        connected_groups.append(current)
    # 转换为列表格式返回
    return [list(g) for g in connected_groups]

def generate_block_list(policy):
    connected_groups = find_connected_groups(policy)
    # 只有一个连通组时，无需要阻断的组合
    if len(connected_groups) <= 1:
        return []
    
    block_set = set()
    # 生成从每个连通组取一个元素的所有组合
    for combo in product(*connected_groups):
        # 排序保证组合一致性（如('B','D')和('D','B')视为同一项）
        sorted_combo = tuple(sorted(combo))
        block_set.add(sorted_combo)
    
    return list(block_set)

# 测试示例
policy1 = [['A'], ['B', 'C'], ['D']]
block_list1 = generate_block_list(policy1)
print("\nPolicy:", policy1)
print("Block List:", block_list1)  # 输出: [('A', 'B', 'D'), ('A', 'C', 'D')]

policy2 = [['A', 'B'], ['B', 'C'], ['D']]
block_list2 = generate_block_list(policy2)
print("\nPolicy:", policy2)
print("Block List:", block_list2)  # 输出: [('A', 'C', 'D'), ('B', 'D')]

policy3 = [['A'], ['B', 'C'], ['D', 'E']]
block_list3 = generate_block_list(policy3)
print("\nPolicy:", policy3)
print("Block List:", block_list3)  # 输出: [('A', 'B', 'D'), ('A', 'B', 'E'), ('A', 'C', 'D'), ('A', 'C', 'E')]

policy4 = [['A'], ['B', 'C'], ['D', 'E'], ['F'], ['G']]
block_list4 = generate_block_list(policy4)
print("\nPolicy:", policy4)
print("Block List:", block_list4)

代码说明 #

1. find_connected_groups函数：通过交集合并所有连通的实体组，比如policy2中的['A','B']和['B','C']会被合并为['A','B','C']，确保连通的实体被归为同一组。
2. generate_block_list函数：
   • 先获取合并后的连通组，若仅一组则无阻断组合。
   • 使用product(*connected_groups)生成跨所有连通组的元素组合，排序后去重保证组合的唯一性。
   • 最终返回符合要求的阻断列表。

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