Calculate power set for a big vector (2^2000) more efficiently

Question

How to improve this function?

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)
}

Test vector

x <- 1:3
powerset(x)

Output

[[1]]
numeric(0)

[[2]]
[1] 1

[[3]]
[1] 2

[[4]]
[1] 1 2

[[5]]
[1] 3

[[6]]
[1] 1 3

[[7]]
[1] 2 3

[[8]]
[1] 1 2 3

"How to change this code?" There are countless ways this code could be changed. There are probably many fewer ways to change it in order to achieve your aim, but you don't tell us what your aim is. — jbaums, Dec 18 '14 at 12:09
I think everyone here is a bit overreacting. OP *did* provide reproducible example and also provided a working code. Using caps is not always meant to offend someone. My guess is that there is some language boundary here, and all he asks is basically to help him vectorise the code. — David Arenburg, Dec 18 '14 at 12:41
possible duplicate of [Algorithm to calculate power set (all possible subsets) of a set in R](http://stackoverflow.com/questions/18715580/algorithm-to-calculate-power-set-all-possible-subsets-of-a-set-in-r) — Henrik, Dec 18 '14 at 12:56
`library(sos)`; `findFn("powerset")`, gives at least three functions which could be worth trying as well. — Henrik, Dec 18 '14 at 12:59
@DavidArenburg - It struck me as demonstrating very little effort, which in turn suggests a lack of respect for our time. Language barriers are an understandable impediment to clearly posed questions, but a sentence or two (even via e.g. Google Translate) describing the OP's intention would not hurt. — jbaums, Dec 18 '14 at 13:03
@jbaums, I think the OP demonstrated more effort than 99% of people asking questions on this site. He actually provided a *working* code. Questions like that you can count on one hand. The only problem here is the language boundary. FYI, many times, Google translate is worse than just saying it in your own language. — David Arenburg, Dec 18 '14 at 13:15
2^2000 is Infinity in R. So I'm not sure how you can do anything efficient with that many numbers. — Spacedman, Dec 18 '14 at 13:43

score 3 · Answer 1 · answered Dec 18 '14 at 12:46

3

Try this:

    powerset<-function(s) {
      n<-length(s)
      do.call(c,lapply(0:n,function(x) combn(s,x,simplify=FALSE)))
    }
    s<-1:3
    powerset(s)

answered Dec 18 '14 at 12:46

nicola

24,005
3
35
56

akrun · Accepted Answer · 2014-12-18T15:04:04.567

If you have really big vector, then combnPrim from gRbase would be more efficient. Same function as @nicola, but replace the combn with combnPrim

 library(gRbase)
 powersetPrim <- function(s) {
  n<-length(s)
   do.call(c,lapply(0:n,function(x) combnPrim(s,x,simplify=FALSE)))
  }
 s<-1:3
 powersetPrim(s)

Benchmark

On a smaller sample

s <- 1:25
microbenchmark(powersetPrim(), powerset(), unit='relative', times=10L)
#Unit: relative
#          expr      min      lq     mean   median       uq      max neval cld
#powersetPrim() 1.000000 1.00000 1.000000 1.000000 1.000000 1.000000    10  a 
#   powerset()  5.254663 4.21187 3.644953 3.386665 2.874453 3.844787    10  b

Calculate power set for a big vector (2^2000) more efficiently

2 Answers2

Benchmark