r - 高效地使用 R 中的集合

Question

背景:

我正在处理 R 中的组合问题。对于给定的集合列表，我需要为每个集合生成所有对而不产生重复项。

例子:

initial_list_of_sets <- list()
initial_list_of_sets[[1]] <- c(1,2,3)
initial_list_of_sets[[2]] <- c(2,3,4)
initial_list_of_sets[[3]] <- c(3,2)
initial_list_of_sets[[4]] <- c(5,6,7)
get_pairs(initial_list_of_sets) 
# should return (1 2),(1 3),(2 3),(2 4),(3 4),(5 6),(5 7),(6 7)

请注意，(3 2) 不包含在结果中，因为它在数学上等于 (2 3)。

到目前为止我的(可行但效率低下的)方法:

# checks if sets contain a_set
contains <- function(sets, a_set){
  for (existing in sets) {
    if (setequal(existing, a_set)) {
      return(TRUE)
    }
  }
  return(FALSE)
}

get_pairs <- function(from_sets){
  all_pairs <- list()
  for (a_set in from_sets) {
    # generate all pairs for current set
    pairs <- combn(x = a_set, m = 2, simplify = FALSE)
    for (pair in pairs) {
      # only add new pairs if they are not yet included in all_pairs
      if (!contains(all_pairs, pair)) {
        all_pairs <- c(all_pairs, list(pair))
      }
    }
  }
  return(all_pairs)
}

我的问题:

当我处理数学集时，我不能使用 %in% 运算符代替我的 contains 函数，因为那时 (2 3) 和 (3 2 ) 将是不同的对。然而，遍历 contains 中的所有现有集合似乎效率很低。有没有更好的方法来实现这个功能？

Answer 1

也许您可以将您的 get_pairs 函数重写为如下所示:

myFun <- function(inlist) {
  unique(do.call(rbind, lapply(inlist, function(x) t(combn(sort(x), 2)))))
}

这是一个快速的时间比较。

n <- 100
set.seed(1)

x <- sample(2:8, n, TRUE)
initial_list_of_sets <- lapply(x, function(y) sample(100, y))

system.time(get_pairs(initial_list_of_sets))
#    user  system elapsed 
#   1.964   0.000   1.959 
system.time(myFun(initial_list_of_sets))
#    user  system elapsed 
#   0.012   0.000   0.014 

如果需要，您可以按行拆分矩阵以获得您的列表。

例如:

myFun <- function(inlist) {
  temp <- unique(do.call(rbind, lapply(inlist, function(x) t(combn(sort(x), 2)))))
  lapply(1:nrow(temp), function(x) temp[x, ])
}