最大化唯一对，包括两个列表中的所有元素

Question

我有一个带有成对元素的 data.frame，第 1 列和第 2 列中的两个元素都可以重复。我想获得最大数量的对，每列都有一个唯一元素，但如果可能的话，所有元素都在 column1 和 column2 中。

> col1 = c("A","A","A","B","C","C")
> col2 = c("X","Y","Z","Y","X","Y")
> df = data.frame(col1,col2)
> df
  col1 col2
1    A    X
2    A    Y
3    A    Z
4    B    Y
5    C    X
6    C    Y

我可以从一列中获得具有唯一值的对，但有时会给出不具有另一列中所有可能值的对。

> df2 = df[!duplicated(df$col1),]
> df2
  col1 col2
1    A    X
4    B    Y
5    C    X

在这种情况下，X在col2中重复，而Z缺失。

我在这种情况下的预期输出是：

  col1 col2
3    A    Z
4    B    Y
5    C    X

是否有任何方法可以最大化对，以便两个列表中的每个元素都出现在对列表中，至少出现一次？

Answer 1

这是一种受最小生成树问题启发的方法：

library(igraph)
g <- graph_from_data_frame(df, FALSE)
MST <- mst(g)

#get leaf nodes
leaves <- which(degree(MST, v=V(MST))==1L, useNames=TRUE)

#get neighbour to each leaf node in a greedy manner starting with leaf nodes with least neighbours
ans <- sapply(adjacent_vertices(MST, sort(leaves)), function(gph) names(gph))

data.table(col1=ifelse(ans %in% df$col1, ans, names(ans)),
    col2=ifelse(ans %in% df$col2, ans, names(ans)))[order(col1)]

方法假设有很多连接，因此每个节点至少有一个连接。

对于 OP，我有兴趣找出失败的边缘情况。请随时通知我。

输出：

   col1 col2
1:    A    Z
2:    B    Y
3:    C    X

最大化唯一对，包括两个列表中的所有元素

Maximizing unique pairs including all elements from both lists

r

duplicates

combinatorics

dataframe