@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; };
No comments:
Post a Comment