Python中如何计算元组b内各元素对应的跨割边数量？

需求说明 #

• a 表示图的全部边集合，每条边是包含两个节点的元组
• b 表示图的所有可能割集，每个割集是一个元组，包含两个互不相交的节点子集，二者的并集为图的所有节点
• 需要计算 b 中每个割集对应的跨割边数（即连接两个节点子集的边的数量），示例如下：
  • 输入：a = ((0,1),(0,2),(0,3))，b = (((0),(1,2,3)), ((0,1),(2,3)), ((0,1,2),(3)))
  • 期望输出：[3,2,1]

原函数问题分析 #

原函数 cnt_edges 统计的是所有割集的跨割边总数，现在需要调整为对每个割集单独统计，返回对应结果的列表。

修改后的实现代码 #

def cnt_cut_edges(a, b):
    # 存储每个割集对应的跨割边数
    cut_edge_counts = []
    # 遍历每个割集
    for cut in b:
        subset1, subset2 = cut
        count = 0
        # 遍历所有边，判断是否属于当前割集的跨边
        for edge in a:
            node1, node2 = edge
            if (node1 in subset1 and node2 in subset2) or (node1 in subset2 and node2 in subset1):
                count += 1
        cut_edge_counts.append(count)
    return cut_edge_counts

# 测试示例
a = ((0, 1),(0, 2), (0,3))
b = (((0),(1,2,3)), ((0,1),(2,3)), ((0,1,2),(3)))
print(cnt_cut_edges(a, b))  # 输出: [3, 2, 1]

代码说明 #

1. 外层循环遍历 b 中的每个割集，将割集拆分为两个节点子集 subset1 和 subset2
2. 内层循环遍历所有边，判断当前边的两个节点是否分别属于两个不同的子集——如果是，则这条边是当前割集的跨割边，计数加1
3. 每个割集的统计完成后，将计数加入结果列表，最后返回整个列表

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