Efficient way to generate permutations of 0 and 1?

Question

What I am trying to do is generate all possible permutations of 1 and 0 given a particular sample size. For instance with a sample of n=8 I would like the m = 2^8 = 256 possible permutations, i.e:

I've written a function in R to do this, but after n=11 it takes a very long time to run. I would prefer a solution in R, but if its in another programming language I can probably figure it out. Thanks!

PermBinary <- function(n){ 
  n.perms <- 2^n 
  array <- matrix(0,nrow=n,ncol=n.perms) 
  # array <- big.matrix(n, n.perms, type='integer', init=-5) 
  for(i in 1:n){ 
    div.length <- ncol(array)/(2^i) 
    div.num <- ncol(array)/div.length 
    end <- 0 
      while(end!=ncol(array)){ 
        end <- end +1 
        start <- end + div.length 
        end <- start + div.length -1 
        array[i,start:end] <- 1 
      } 
   } 
   return(array) 
}

Sure! ` PermBinary <- function(n){ n.perms <- 2^n array <- matrix(0,nrow=n,ncol=n.perms) # array <- big.matrix(n, n.perms, type='integer', init=-5) for(i in 1:n){ div.length <- ncol(array)/(2^i) div.num <- ncol(array)/div.length end <- 0 while(end!=ncol(array)){ end <- end +1 start <- end + div.length end <- start + div.length -1 array[i,start:end] <- 1 } } return(array) } ` — Alejandro Ochoa, Aug 06 '15 at 16:24
What about using `expand.grid`? http://stackoverflow.com/questions/9422945/generate-all-possible-permutations — robert, Aug 06 '15 at 16:24

Dason · Answer 1 · 2015-08-06T16:37:16.210

expand.grid is probably the best vehicle to get what you want.

For example if you wanted a sample size of 3 we could do something like

expand.grid(0:1, 0:1, 0:1)

For a sample size of 4

expand.grid(0:1, 0:1, 0:1, 0:1)

So what we want to do is find a way to automate that call.

If we had a list of the inputs we want to give to expand.grid we could use do.call to construct the call for us. For example

vals <- 0:1
tmp <- list(vals, vals, vals)
do.call(expand.grid, tmp)

So now the challenge is to automatically make the "tmp" list above in a fashion that we can dictate how many copies of "vals" we want. There are lots of ways to do this but one way is to use replicate. Since we want a list we'll need to tell it to not simplify the result or else we will get a matrix/array as the result.

vals <- 0:1
tmp <- replicate(4, vals, simplify = FALSE)
do.call(expand.grid, tmp)

Alternatively we can use rep on a list input (which I believe is faster because it doesn't have as much overhead as replicate but I haven't tested it)

tmp <- rep(list(vals), 4)
do.call(expand.grid, tmp)

Now wrap that up into a function to get:

binarypermutations <- function(n, vals = 0:1){
    tmp <- rep(list(vals), n)
    do.call(expand.grid, tmp)
}

Then call with the sample size like so binarypermutations(5).

This gives a data.frame of dimensions 2^n x n as a result - transpose and convert to a different data type if you'd like.

score 3 · Answer 2 · answered Aug 06 '15 at 16:36

3

The answer above may be better since it uses base - my first thought was to use data.table's CJ function:

library(data.table)
do.call(CJ, replicate(8, c(0, 1), FALSE))

It will be slightly faster (~15%) than expand.grid, so it will only be more valuable for extreme cases.

answered Aug 06 '15 at 16:36

Señor O

17,049
2
45
47

It won't make much of a difference since it's not where most of the time is spent but I did just do the benchmarking and using `rep` on list input is about 20x faster than using `replicate` – Dason Aug 06 '15 at 16:46

Efficient way to generate permutations of 0 and 1?

2 Answers2