10

I would like to create all possible combinations of a binary vector of length n > 2 with the property that the maximum number of 1's in the row is 2.

For example:

If n=4, the answer would be:

0 0 0 0 
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 0 1
1 0 1 0
1 1 0 0

This works but gets very memory intensive and slow as n gets large (n>20):

n <- 4
m <- expand.grid(rep(list(0:1),n))
m <- m[rowSums(m)<3,]

How can I do this more efficiently?

Answer:
*Based on a combination of Marat Talipov's and akrun's solutions

n=4
z=rep(0,n)
rbind(unname(z), t(combn(0:n,2, FUN=function(k) {z[k]=1;z})))
verigolfer
  • 359
  • 1
  • 10
  • @akrun I think my problem is that as n gets larger, `expand.grid` unnecessarily creates rows that will be removed in the next step. Preferably, these vectors wouldn't be created in the first place. – verigolfer Jan 07 '15 at 19:01
  • 2
    For starters, `Reduce("+", m)` is by several factors more efficient than `rowSums(m)` – David Arenburg Jan 07 '15 at 19:01
  • for exact two ;) library(multcomp); n <- 10; nn <- 1:n; m <- contrMat(nn, type="Tukey"); m[m==-1] = 1 – ckluss Jan 07 '15 at 19:14
  • 1
    @verigolfer Another option for bigger datasets will be `combnPrim` from `library(grBase)`. It is very fast compared to `combn` Please check http://stackoverflow.com/questions/26828301/faster-version-of-combn/26828486#26828486 – akrun Jan 07 '15 at 19:22

1 Answers1

6

This algorithm might be be more effective than that based on expand.grid:

n <- 3
z <- rep(0,n)

answer <- t(apply(combn(0:n,2),2,function(k) {z[k]=1;z}))
#      [,1] [,2] [,3]
# [1,]    1    0    0
# [2,]    0    1    0
# [3,]    0    0    1
# [4,]    1    1    0
# [5,]    1    0    1
# [6,]    0    1    1

[EDIT] I noticed that my original solution misses a trivial case of all zeros, which can be easily fixed:

rbind(unname(z),answer)
#       [,1] [,2] [,3] [,4]
#  [1,]    0    0    0    0
#  [2,]    1    0    0    0
#  [3,]    0    1    0    0
#  [4,]    0    0    1    0
#  [5,]    0    0    0    1
#  [6,]    1    1    0    0
#  [7,]    1    0    1    0
#  [8,]    1    0    0    1
#  [9,]    0    1    1    0
# [10,]    0    1    0    1
# [11,]    0    0    1    1
Marat Talipov
  • 13,064
  • 5
  • 34
  • 53