如何从两列唯一行DataFrame中提取最大行数的唯一值子集

现有一个2列的DataFrame，包含1300条唯一行：

• 第一列有160个唯一值
• 第二列有230个唯一值

需要提取该DataFrame的一个子集，满足两个条件：

1. 子集的第一列所有值唯一，第二列所有值也唯一
2. 子集的行数尽可能多

示例DataFrame（R代码） #

subject1 = c("A","B","C","D")
subject2 = c("0","1")
df = expand.grid(V1 = subject1, V2 = subject2)
df = df[-5,] # 删除一行，让DataFrame不包含所有可能的组合
# 此时df内容：
#   V1 V2
# 1  A  0
# 2  B  0
# 3  C  0
# 4  D  0
# 6  B  1
# 7  C  1
# 8  D  1

符合要求的示例输出 #

满足条件的最大行数子集可以是：

V1 V2
  B  0
  C  1

或者：

V1 V2
  D  1
  A  0

其他任何符合两列值均唯一的最大行数组合都有效。

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

• 把第一列的唯一值作为二分图的左顶点集
• 把第二列的唯一值作为二分图的右顶点集
• DataFrame中的每一行对应左顶点到右顶点的一条边

找到二分图的最大匹配后，匹配对应的边就是满足条件的最大行数子集。

以下是用R语言实现的步骤：

1. 安装并加载依赖包 #

if (!require(igraph)) {
  install.packages("igraph")
  library(igraph)
}

2. 构建二分图并计算最大匹配 #

# 假设你的原始DataFrame名为original_df，列名为V1和V2

# 构建二分图
graph <- graph_from_data_frame(original_df, directed = FALSE)
V(graph)$type <- bipartite_mapping(graph)$type # 标记二分图的两个顶点集

# 计算最大匹配
max_matching <- max_bipartite_matching(graph)

# 提取匹配对应的键值对
matched_pairs <- data.frame(
  V1 = names(max_matching$matching)[max_matching$type],
  V2 = max_matching$matching[max_matching$type]
)

# 从原始DataFrame中筛选出匹配的行
result_df <- merge(original_df, matched_pairs, by = c("V1", "V2"))

结果说明 #

最终的result_df就是满足条件的最大行数子集，其行数等于二分图最大匹配的大小——这个值不会超过第一列唯一值数量（160）和第二列唯一值数量（230）中的较小值，也就是最多160行（如果原始DataFrame存在足够的边支撑该匹配）。

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