CODEWITHSUNDEEP
ralgorithmpermutation
Alejandro Ochoa
Alejandro Ochoa

Reputation: 248

Efficient way to generate permutations of 0 and 1?

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:

Possible permutations of 1 and 0 with n=8

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

Upvotes: 2

Views: 1138

Answers (2)

Dason
Dason

Reputation: 61933

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.

Upvotes: 5

Se&#241;or O
Se&#241;or O

Reputation: 17412

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.

Upvotes: 3

Related Questions