Python中嵌套元组的边交集数量统计问题

核心思路 #

要解决这个问题，关键是判断每条边是否连接了s中对应元组的两个内部子元组。具体来说，对于s中的每个元素（形如(A, B)），我们需要统计f中满足以下条件的边：边的一个端点在A的集合中，另一个端点在B的集合中（边是无向的，两种方向都要考虑）。

实现步骤 #

1. 对s中的每个二元组(A, B)，将A和B转换为集合（集合的成员查询效率远高于元组）。
2. 遍历f中的每条边(u, v)，检查是否满足(u ∈ A且v ∈ B) 或 (u ∈ B且v ∈ A)。
3. 统计每个s元素对应的符合条件的边数，最终得到结果列表。

代码实现 #

结合你已有的代码，完整的实现如下：

# 读取输入并转换为嵌套元组（你的原有代码）
x = int(input())
f = []
for i in range(x):
    a, b = map(int, input().split())
    f.append([a,b])

def to_tuple(lst):
    return tuple(to_tuple(i) if isinstance(i, list) else i for i in lst)

f = to_tuple(f)
# 假设s是已经生成的嵌套元组（示例中的s）
s = (((0,), (1, 2, 3)), ((0, 1), (2, 3)), ((0, 1, 2), (3,)))

# 定义统计函数
def count_cross_edges(edges, partition):
    set_left = set(partition[0])
    set_right = set(partition[1])
    count = 0
    for u, v in edges:
        # 检查边是否跨两个分区
        if (u in set_left and v in set_right) or (u in set_right and v in set_left):
            count += 1
    return count

# 生成结果列表
result = [count_cross_edges(f, item) for item in s]
print(result)  # 输出: [3, 3, 1]

逻辑验证 #

针对示例中的数据：

• 第一个分区((0,), (1,2,3))：符合条件的边是(0,1)、(0,2)、(0,3)，共3条。
• 第二个分区((0,1), (2,3))：符合条件的边是(1,2)、(0,2)、(0,3)，共3条。
• 第三个分区((0,1,2), (3,))：符合条件的边是(0,3)，共1条。

完全匹配预期输出[3,3,1]。

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