我有一对。每对表示为 [i,1:2]
。也就是说,第 ith<
对是第 ith<
行中第一列和第二列中的数字。
我需要将这些对分成不同的组,s.t. jth
组中的任何对中没有任何元素不在 j
组中。例如:
示例 1:数据
> col1 <- c(3, 4, 6, 7, 10, 8)
> col2 <- c(6, 7, 3, 4, 3, 1)
>
> dat <- cbind(col1, col2)
> rownames(dat) <- 1:nrow(dat)
>
> dat
col1 col2
1 3 6
2 4 7
3 6 3
4 7 4
5 10 3
6 8 1
对于所有的对,数字是在第 1 列还是第 2 列并不重要,这些对应该被分类到组 s.t.每组中每对中的每个数字仅存在于一个组中。所以解决的例子看起来像这样。
col1 col2 groups
1 3 6 1
2 4 7 2
3 6 3 1
4 7 4 2
5 10 3 1
6 8 1 3
第 1、3 和 5 行被组合在一起,因为 1 和 3 包含相同的数字,而 5 共享数字 3,因此它必须与它们组合在一起。 2 和 4 共享相同的不同编号,因此将它们组合在一起,而 6 具有唯一编号,因此单独放置。
如果我们稍微更改数据,请注意以下事项。
示例 2:新数据
请注意当我们添加与第 6 行和第 5 行共享一个元素的行时会发生什么。
col1 col2 groups
1 3 6 1
2 4 7 2
3 6 3 1
4 7 4 2
5 10 3 1
6 8 1 1
7 1 10 1
第 7 行的 10
将它连接到第一组,因为它与第 5 行共享一个元素。它还与第 6 行共享一个元素(数字 1
),因此第 6 行将改为在组 1 中。
问题
有没有简单的组队方法?矢量运算?排序算法?如果您尝试使用循环执行此操作,它会很快变得非常讨厌,因为每个后续行都可以更改前面行的成员资格,如示例中所示。
最佳答案
利用旧答案:identify groups of linked episodes which chain together ,它为每个单独的值分配一个组,您可以尝试为每个链接对分配一个组:
library(igraph)
g <- graph_from_data_frame(dat)
links <- data.frame(col1=V(g)$name,group=components(g)$membership)
merge(dat,links,by="col1",all.x=TRUE,sort=FALSE)
# col1 col2 group
#1 3 6 1
#2 4 7 2
#3 6 3 1
#4 7 4 2
#5 10 3 1
#6 8 1 3
关于r - 从一组对中,找到所有子集 s.t.子集中没有对与不在子集中的对共享任何元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25173752/