合并在R中共享元素的列出的向量

Question

谢谢你的帮助。我正在尝试编写一个R函数，它将获取包含数字向量的列表并合并所有共享数字的列表元素。我不确定我是否正确解释了这个问题，所以我希望你不要介意我是否使用类比。示例列表可能如下所示：

> list(c(1, 6), c(2, 3), c(3, 2), c(4, 5, 6), c(5, 4), c(1, 6, 4))
[[1]]
[1] 1 6

[[2]]
[1] 2 3

[[3]]
[1] 3 2

[[4]]
[1] 4 5 6

[[5]]
[1] 5 4

[[6]]
[1] 1 6 4

如果您想象6个村庄，列表将显示哪些村庄通过道路连接。因此，列表元素[[1]]显示村庄1连接到村庄1和村庄6.列表元素[[6]]显示6连接到村庄1，村庄6和村庄4.依此类推。我希望我的输出显示哪个村庄通过相同的“道路网络”连接，因此村庄1显然与6在同一网络中，但它也应该与4和5分组，因为它通过6和6连接到它们然后4. 2和3应单独分组，因为它们不共享与其他网络的连接。

我已经设法拼凑出一个解决方案，但它非常不优雅，并且需要太长时间才能运行更复杂的输入。我的解决方案是：

input <- list(c(1, 6), c(2, 3), c(3, 2), c(4, 5, 6), c(5, 4), c(1, 6, 4))
remaining <- 1:6                  # counter where i can store which numbers have not yet been evaluated
output <- vector("list", 6)

branch <- function(x) {           # function to recursively evaluate vector elements
  for(y in x) {                                           # repeat for each vector element
    if(y %in% remaining) {                                # check if the list element corresponding to y has been evaluated
      output[[i]] <- append(output[[i]], input[[y]])      # assign list element y to output element i
      assign("output", output, envir = globalenv())       #assign output to global environment
      remaining <- remaining[remaining != y]              # remove y from future evaluations
      assign("remaining", remaining, envir = globalenv()) # assign remaining to global environment
      branch(input[[y]])                                  # evaluate branches further from y
    }
  }
}

for(i in 1:6) {                    # repeat for each element of list
  if(i %in% remaining) {           # check if list element i has already been evaluated
    branch(input[[i]])             # evaluate list element
  }
}

output <- output[-which(sapply(output, is.null))]         # remove null elements from list
output <- lapply(output, unique)                          # remove redundant elements from vectors

output

> output
[[1]]
[1] 1 6 4 5

[[2]]
[1] 2 3

很抱歉这个问题很长，但我觉得必须有一个更简单的方法来做到这一点，我很想念。有人能帮忙吗？

Answer 1

正如评论中所提到的，你的问题基本上是你需要构建一个图并找到它的组件 - 所以igraph非常有用。

事实证明，您的数据已经或多或少地采用了正确的格式，因此您可以：

library(igraph)

input <- list(c(1, 6), c(2, 3), c(3, 2), c(4, 5, 6), c(5, 4), c(1, 6, 4))

# mode = "all" so that connections are treated as two-way,
#   i.e. an 'undirected' graph
g = graph_from_adj_list(input, mode = "all")
comp = components(g)
groups(comp)

输出：

$`1`
[1] 1 4 5 6

$`2`
[1] 2 3

您还可以使用plot(g)轻松实现图形可视化：

PS：它不会影响这个简单的例子，但是图形确实包含一个循环，其中1连接到自身 - 您可能需要从输入数据中过滤这些自连接。