r - 用于计算R中集合的幂集(所有可能的子集)的算法

Question

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

问题是:如何计算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)
}

该版本通过在起始位置起始向量的最终长度并跟踪保存新子集的位置的“counter”变量来节省时间。也可以通过分析来计算位置，但是速度稍慢一些。

Answer 1

子集可以视为 bool 向量，指示元素是否在not的子集中。
这些 bool 向量可以看成是以二进制形式写的数字。
枚举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])