R语言如何合并无序列表中交集元素并去除冗余

这个问题可以转化为无向图连通分量求解：将每个出现的整数作为图节点，同一向量内的所有整数标记为连通状态，最终归集同一连通分量的所有节点即可，逻辑完全不依赖列表元素的排列顺序，同时自动去重重复的冗余向量。

下面是基于并查集实现的可直接使用的函数，带路径压缩优化，大列表场景下运行效率很高：

merge_intersect_sets <- function(lst) {
  # 提取所有出现的唯一整数
  all_nodes <- unique(unlist(lst))
  # 初始化并查集父节点映射
  parent <- setNames(all_nodes, as.character(all_nodes))

  # 带路径压缩的根节点查找
  find_root <- function(x) {
    x_chr <- as.character(x)
    while (parent[[x_chr]] != x) {
      parent[[x_chr]] <<- parent[[as.character(parent[[x_chr]])]]
      x <- parent[[x_chr]]
      x_chr <- as.character(x)
    }
    x
  }

  # 合并两个节点所在集合
  union_nodes <- function(a, b) {
    root_a <- find_root(a)
    root_b <- find_root(b)
    if (root_a != root_b) {
      parent[[as.character(root_b)]] <<- root_a
    }
  }

  # 遍历所有向量，合并连通节点
  for (vec in lst) {
    vec_len <- length(vec)
    if (vec_len <= 1) next
    ref <- vec[1]
    for (val in vec[2:vec_len]) {
      union_nodes(ref, val)
    }
  }

  # 按连通分量分组，排序整理结果
  comps <- split(all_nodes, sapply(all_nodes, find_root))
  res <- lapply(comps, function(x) sort(as.integer(x)))
  # 按分量最小值排序，和示例输出顺序对齐，不需要可删除该行
  res <- res[order(sapply(res, min))]
  names(res) <- NULL
  res
}

效果验证 #

测试1：原始顺序输入 #

ll_1 <- list(c(1,4), c(5,7,3,9), c(5,3,7,9), c(2,7,10), 8, 6)
merge_intersect_sets(ll_1)

运行输出和预期结果完全匹配：

[[1]]
[1] 1 4

[[2]]
[1]  2  3  5  7  9 10

[[3]]
[1] 6

[[4]]
[1] 8

测试2：打乱列表元素顺序输入 #

ll_2 <- list(c(2,7,10), c(1,4), c(5,7,3,9), 8, 6, c(5,3,7,9))
merge_intersect_sets(ll_2)

输出和测试1完全一致，不会因为元素排列顺序变化产生错误结果，重复的冗余向量会被自动去重。

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