Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Create all possible combiations of 0,1, or 2 "1"s of a binary vector of length n

Tags:

r

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})))
like image 362
verigolfer Avatar asked Jan 07 '15 18:01

verigolfer


1 Answers

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
like image 185
Marat Talipov Avatar answered Oct 05 '22 03:10

Marat Talipov