r语言 - 从对的集合中，找出所有的子集s.t.在子集中没有对与不在子集中的对共享任何元素

Question

我有一组对。每一对表示为[i,1:2]。也就是说，ith对是ith行第一列和第二列的数字。

我需要将这些对排序到不同的组中，s.t. jth组中任何对中的元素都不属于j以外的任何组。例如:

示例1:DATA

> 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

对于所有的对，无论数字在第一列还是第二列，都应该将它们分成组，每组中每对中的每一个数字只存在于一个组中。所以解出的例子是这样的。

  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将它连接到第1组，因为它与第5行共享一个元素。它还与第6行共享一个元素(数字1)，因此第6行将在第1组中。

是否有一种简单的方法来形成组?矢量运算?排序算法?如果您尝试使用循环来执行此操作，那么很快就会变得非常糟糕，因为后续的每一行都可以更改前一行的成员关系，如示例中所示。

Answer 1

要利用旧的答案:识别链接在一起的剧集组，它为每个单独的值分配一个组，您可以尝试为每个链接对分配一个组:

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

Answer 2

你的元素可以被视为无向图中的顶点，你的对可以被视为边，然后(假设你想找到最小大小的组——如果你不这样做，那么例如，整个组对可以被标记为"组1")你正在寻找的组是这个图中的连接组件。它们都可以在线性时间内通过深度优先或宽度优先的搜索找到。