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