含element1与element2双字段数据集如何在element1不重复时保留最多唯一element2值

解决方案 #

核心思路 #

该问题属于经典的二分图最大匹配问题：

1. 将所有唯一的element1值作为二分图左节点
2. 将所有唯一的element2值作为二分图右节点
3. 原始数据中每一组存在的(element1, element2)对应左右节点之间的一条边
4. 求解二分图的最大匹配，得到的结果就是符合要求的筛选结果，此时保留的唯一element2值数量最多

代码实现（Python） #

可以使用networkx库快速实现上述逻辑：

import networkx as nx

# 替换为你的实际数据集
raw_data = [
    ("A", 1), ("B", 1), ("C", 1),
    ("A", 2), ("C", 2),
    ("D", 4), ("D", 5), ("D", 6)
]

# 初始化二分图
graph = nx.Graph()
e1_nodes = {item[0] for item in raw_data}
e2_nodes = {item[1] for item in raw_data}
graph.add_nodes_from(e1_nodes, bipartite=0)
graph.add_nodes_from(e2_nodes, bipartite=1)
graph.add_edges_from(raw_data)

# 计算最大匹配
max_matching = nx.bipartite.maximum_matching(graph, top_nodes=e1_nodes)

# 转换为最终筛选结果
filter_result = [(e1, max_matching[e1]) for e1 in e1_nodes if e1 in max_matching]
print(filter_result)

如果需要获取所有符合要求的最大匹配方案，可以调用nx.bipartite.all_maximal_matching方法遍历全部可行解。

内容的提问来源于stack exchange，提问作者Hugo González