Friday 11 January 2013

Generating all binary arrays of a given length in Coffeescript / Javascript

The following Coffeescript code generates an array containing every possible binary array of a certain length:

@allVectors = (n) ->
    vectors = []
    return vectors if n == 0
    vectors[0] = [0]
    vectors[1] = [1]
    return vectors if n == 1
    for i in [0..n-2]
        count = vectors.length
        for j in [0..count-1] 
            vectors[j+count] = vectors[j][..] #Copy the array to a new location
            vectors[j].push 0 #In the first copy add a 0 on the end
            vectors[j+count].push 1 #In the second copy add a 1 on the end
    return vectors

For example, calling allVectors(2) will return [[0,0],[0,1],[1,0],[1,1]].

This runs in O(n2^n) time. Can you do it faster? Got a prettier implementation? Lets see them in the comments!

(Here it is compiled into Javascript for any old school coders around:)

allVectors = function(n) {
  var count, i, j, vectors, _i, _j, _ref, _ref1;
  vectors = new Array();
  if (n === 0) {
    return vectors;
  }
  vectors[0] = new Array();
  vectors[1] = new Array();
  vectors[0][0] = 0;
  vectors[1][0] = 1;
  if (n === 1) {
    return vectors;
  }
  for (i = _i = 0, _ref = n - 2; 0 <= _ref ? _i <= _ref : _i >= _ref; i = 0 <= _ref ? ++_i : --_i) {
    count = vectors.length;
    for (j = _j = 0, _ref1 = count - 1; 0 <= _ref1 ? _j <= _ref1 : _j >= _ref1; j = 0 <= _ref1 ? ++_j : --_j) {
      vectors[j + count] = vectors[j].slice(0);
      vectors[j][vectors[j].length] = 0;
      vectors[j + count][vectors[j + count].length] = 1;
    }
  }
  return vectors;
};