对于集合列表:如何标识所有属于另一个列表成员的适当子集的成员？

Question

请考虑以下列表，其中每个成员都包含一组数字。

sets <- list(a=1:3, b=2:3, c=4:6, d=4:6, e=7)

我想识别列表中另一个集合的适当子集，以便我想要的结果如下……

c(F,T,F,F,F)

因为我的实际集合相当大，所以我不想计算每个集合的幂集。有没有人想过一种有效的方法来做到这一点？

这就是我到目前为止所做的工作，但这不可能是最优雅的方法。

 truthtable <- bind_rows(lapply(X=sets, FUN=function(x, allsets){
  unlist(lapply(X=allsets, FUN=function(x,testset){
    return(all(x %in% testset) & !setequal(x, testset))
  }, testset=x))
}, allsets=sets))

apply(truthtable, 1, function(x){(all(!x))})

Answer 1

我不知道allsets是从哪里来的，但是您的总体方法看起来还不错。下面是一个使用简单for循环的重构版本：

is_proper_subset = function(x, y) {
  all(x %in% y) && !setequal(x, y)
}

result = rep(NA, length(sets))
for (i in seq_along(sets)) {
  result[i] = any(sapply(sets[-i], is_proper_subset, x = sets[[i]]))
}
result
# [1] FALSE  TRUE FALSE FALSE FALSE

Answer 2

为了快速地对集合进行操作，请使用二元决策图。

在对所需集合的操作的函数中，可以选择不同的BSD变体。在最一般的情况下，在终端节点上使用每个集合的ID，而不统一终端节点。

有数千篇不同的文章可以让您学习如何实现它们；与列表和其他琐碎的数据结构相比，要实现BSD，您有很多不同的方法，还有更多的脑力来使用它们，但是在您理解了它们之后，您会喜欢这种数据结构。

这是一个很大的智力努力去理解它，但是当你按照你的意愿实现一组集合，一组集(powerset)时，它会运行得非常快。