如何在DataFrame中找出两列的最大唯一匹配对集合

问题说明 #

给定含X、Y两列的DataFrame，需找出数量最多的唯一匹配对集合，约束规则：

• 单个X值仅能匹配一个Y值
• 单个Y值仅能匹配一个X值

示例输入 #

预期输出 #

核心思路 #

这本质是二分图最大匹配问题：

• 把X的唯一值作为左顶点集，Y的唯一值作为右顶点集
• 原DataFrame的每一行(X,Y)对应二分图中的一条边
• 求解最大匹配就能得到满足约束的最多配对数

实现方案（Python） #

用networkx库可以快速求解，步骤如下：

1. 构建二分图 #

import pandas as pd
import networkx as nx

# 初始化示例DataFrame
df = pd.DataFrame({
    'X': [1,1,2,2,3,3,4,4,4,5,5],
    'Y': ['a','b','c','d','b','a','c','d','e','e','c']
})

# 创建二分图对象
G = nx.Graph()
# 区分左右节点（加前缀避免重名）
left_nodes = [f"X_{x}" for x in df['X'].unique()]
right_nodes = [f"Y_{y}" for y in df['Y'].unique()]
G.add_nodes_from(left_nodes, bipartite=0)
G.add_nodes_from(right_nodes, bipartite=1)

# 添加所有边
for _, row in df.iterrows():
    G.add_edge(f"X_{row['X']}", f"Y_{row['Y']}")

2. 计算最大匹配并转换格式 #

# 求解最大匹配
max_matching = nx.bipartite.maximum_matching(G, left_nodes=left_nodes)

# 转换为原始X、Y格式
result = []
for x_node, y_node in max_matching.items():
    if x_node.startswith('X_'):
        result.append({
            'X': int(x_node.split('_')[1]),
            'Y': y_node.split('_')[1]
        })

# 整理成有序的DataFrame
result_df = pd.DataFrame(result).sort_values('X').reset_index(drop=True)
print(result_df)

运行结果 #

输出与预期一致：

X  Y
0  1  a
1  2  c
2  3  b
3  4  d
4  5  e

补充说明 #

• 若无法使用networkx，可手动实现匈牙利算法，但库的实现效率更高，适合快速解决问题
• 该方法保证找到数量最多的匹配对；若存在多个等价的最大匹配（不同配对但数量相同），此方法会返回其中一种，如需所有可能结果可扩展逻辑

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