从 R 中的集合列表中快速检索任意集合的所有子集

Question

有没有一种方法可以在 R 中快速检索列表中集合的所有严格子集（例如，二进制编码为矩阵的子集，其中每行代表一个子集）？我认为一棵树就足够了，但我想知道

1. 有没有一个包可以做这类事情并且
2. 如果没有，如何在 R 中编写树？我已经在 C++ 中完成了此操作，但几乎没有在 R 中尝试过任何更高级的数据结构。

数据的一个示例是包含两个元素的列表：[{a,b}, {a,b,c}]。这可以用 R 写成：

matrix(c(1,1,0,1,1,1),nrow = 2)

我们想要一个函数

subset(A)

为：

c(1,1,1)

的子集应该给出

matrix(c(1,1,0), nrow=1)

，因为列表中只有第一个集合是它的严格子集。

c(1,1,0)

的子集应该给出

NULL

，因为列表中没有集合是它的严格子集。

一个类似的问题是 Fast Data Structure for Find严格子集（从给定列表中）但在这个问题中我们有兴趣在 R 中对其进行编程。

Answer 1

也许您可以尝试像下面那样使用

tcrossprod

+

rowSums

来查找所有子集，然后应用

colMeans

来过滤“严格子集”，例如，

f <- function(mat, v) {
  d <- mat[tcrossprod(v, mat) == rowSums(mat), , drop = FALSE]
  d[colMeans(t(d) == v) < 1, , drop = FALSE]
}

示例

给定数据

mat

喜欢

> set.seed(1)

> (mat <- unique(matrix(sample(c(0, 1), 100, replace = TRUE), nrow = 20)))
      [,1] [,2] [,3] [,4] [,5]
 [1,]    0    0    1    0    1
 [2,]    1    0    1    1    1
 [3,]    0    0    0    1    0
 [4,]    0    0    1    1    0
 [5,]    1    0    1    1    0
 [6,]    0    0    1    1    1
 [7,]    0    1    1    1    0
 [8,]    1    0    0    1    0
 [9,]    1    1    0    1    1
[10,]    0    1    0    1    0
[11,]    0    1    1    0    1
[12,]    0    0    0    0    0
[13,]    1    1    1    1    0
[14,]    1    0    1    0    1
[15,]    1    1    1    0    1

我们可以获得

> f(mat, c(0, 1, 1, 1, 1))
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    1    0    1
[2,]    0    0    0    1    0
[3,]    0    0    1    1    0
[4,]    0    0    1    1    1
[5,]    0    1    1    1    0
[6,]    0    1    0    1    0
[7,]    0    1    1    0    1
[8,]    0    0    0    0    0

> f(mat, c(0, 1, 0, 1, 0))
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    1    0
[2,]    0    0    0    0    0

> f(mat, c(1, 1, 0, 1, 1))
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    1    0
[2,]    1    0    0    1    0
[3,]    0    1    0    1    0
[4,]    0    0    0    0    0