用于计算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)
}

该版本通过在开始时以其最终长度启动向量并使用保存新子集的位置的"计数器"变量来跟踪来节省时间.也可以通过分析计算位置,但稍微慢一点.

Answer 1

子集可以被视为布尔向量,指示元素是否在非子集中.那些布尔向量可以看作是用二进制写的数字.枚举所有的子集,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])