10

我在任何地方都找不到答案，所以这是我的解决方案。

问题是：如何计算 R 中的幂集？

可以使用库“sets”执行此操作，使用命令2^as.set(c(1,2,3,4))产生输出{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}。但是，这使用了递归算法，速度相当慢。

这是我想出的算法。

它是非递归的，因此它比其他一些解决方案快得多（在我的机器上比“sets”包中的算法快约 100 倍）。速度仍然是 O(2^n)。

该算法的概念基础如下：

for each element in the set:
    for each subset constructed so far:
        new subset = (subset + element)

这是R代码：

编辑：这是同一概念的更快版本；我的原始算法在这篇文章的第三条评论中。对于一组长度为 19 的机器，这个在我的机器上快 30%。

powerset = function(s){
    len = length(s)
    l = vector(mode="list",length=2^len) ; l[[1]]=numeric()
    counter = 1L
    for(x in 1L:length(s)){
        for(subset in 1L:counter){
            counter=counter+1L
            l[[counter]] = c(l[[subset]],s[x])
        }
    }
    return(l)
}

此版本通过在开始时使用其最终长度初始化向量并跟踪保存新子集的位置的“计数器”变量来节省时间。也可以通过分析计算位置，但速度稍慢。

4

4 回答 4

13

子集可以看成是一个布尔向量，表示一个元素是否在子集中。这些布尔向量可以看作是用二进制编写的数字。因此，枚举 的所有子集1:n 等同于枚举从0到的数字2^n-1。

f <- function(set) { 
  n <- length(set)
  masks <- 2^(1:n-1)
  lapply( 1:2^n-1, function(u) set[ bitwAnd(u, masks) != 0 ] )
}
f(LETTERS[1:4])
于 2013-09-10T11:42:47.677 回答
4

powerset包中有一个函数HapEstXXR似乎比你的函数和另一个答案中的函数更快。见下文（您的函数被调用your.powerset）

require('microbenchmark')
require('HapEstXXR')
microbenchmark(powerset(LETTERS[1:10]), f(LETTERS[1:10]), your.powerset(LETTERS[1:10]), times=100)


Unit: microseconds
                         expr      min        lq    median        uq       max neval
      powerset(LETTERS[1:10])  314.845  388.4225  594.2445  686.6455   857.513   100
             f(LETTERS[1:10]) 7144.132 7937.6040 8222.1330 8568.5120 17805.335   100
 your.powerset(LETTERS[1:10]) 5016.981 5564.2880 5841.9810 6025.0690 29138.763   100

由于powerset似乎非常快，您可能需要查看HapEstXXR包中函数的代码。

于 2013-09-10T12:48:29.333 回答
2

这是另一种简单的方法，它似乎对小集合表现得相当好。随着数据基数的增加，这种方法存在明显的内存问题。

getPowSet <- function(set) {     
  n <- length(set)
  keepBool <- sapply(2^(1:n - 1), function(k) 
    rep(c(FALSE, TRUE), each=k, times=(2^n / (2*k))))
  lapply(1:2^n, function(j) set[keepBool[j, ]])
}

速度比较n=10：

microbenchmark(powerset(LETTERS[1:10]), f(LETTERS[1:10]), getPowSet(LETTERS[1:10]))

Unit: milliseconds
                     expr      min       lq     mean   median       uq      max neval
  powerset(LETTERS[1:10]) 2.466167 2.551928 2.656964 2.581211 2.637358 3.676877   100
         f(LETTERS[1:10]) 2.923339 3.029928 3.115222 3.104413 3.175931 4.033136   100
 getPowSet(LETTERS[1:10]) 2.415290 2.490522 2.574131 2.547115 2.617198 3.664040   100

但是对于n=15原始功能似乎表现更好：

microbenchmark(powerset(LETTERS[1:15]), f(LETTERS[1:15]), getPowSet(LETTERS[1:15]))

Unit: milliseconds
                     expr       min        lq      mean    median       uq      max neval
  powerset(LETTERS[1:15])  81.48276  88.50272  94.88927  91.61366  94.8262 174.0636   100
         f(LETTERS[1:15]) 110.86208 118.08736 124.38501 122.35872 126.7830 189.3131   100
 getPowSet(LETTERS[1:15])  86.16286  93.32314  98.14936  96.85443 100.6075 159.1030   100
于 2015-08-24T17:10:36.447 回答
1

下面应该创建一个幂集，减去空集元素。

powerset <- function(x) {
  sets <- lapply(1:(length(x)), function(i) combn(x, i, simplify = F))
  unlist(sets, recursive = F)
}
于 2018-09-06T21:24:43.323 回答