Generating Combinations in Ruby and Javascript

Hey, time to dust off your discrete math text! (The one I used is Discrete Mathematics and Its Applications by Kenneth H. Rosen). The number of combinations of r items that can be selected from n items is given by the formula = n!/r!(n - r)! (note to self, render this with MathML). The following three code blocks show how to return those combinations in Ruby, Javascript, and Javascript with Prototype. Note that these functions yield (in Ruby) or do a callback with (Javascript) each combination. These could easily be modified to return an array of the combinations. After the three code snippets is a live example of the Javascript code. First the Ruby:

	def generate_combinations(array, r)
	n = array.length
	indices = (0...r).to_a
	final = (n - r...n).to_a
	while indices != final
	yield indices.map {|k| array[k]}
	i = r - 1
	while indices[i] == n - r + i
	i -= 1
	end
	indices[i] += 1
	(i + 1...r).each do |j|
	indices[j] = indices[i] + j - i
	end
	end
	yield indices.map {|k| array[k]}
	end

view raw gistfile1.rb hosted with ❤ by GitHub

Now the Javascript:

	function generateCombinations(array, r, callback) {
	function equal(a, b) {
	for (var i = 0; i < a.length; i++) {
	if (a[i] != b[i]) return false;
	}
	return true;
	}
	function values(i, a) {
	var ret = [];
	for (var j = 0; j < i.length; j++) ret.push(a[i[j]]);
	return ret;
	}
	var n = array.length;
	var indices = [];
	for (var i = 0; i < r; i++) indices.push(i);
	var final = [];
	for (var i = n - r; i < n; i++) final.push(i);
	while (!equal(indices, final)) {
	callback(values(indices, array));
	var i = r - 1;
	while (indices[i] == n - r + i) i -= 1;
	indices[i] += 1;
	for (var j = i + 1; j < r; j++) indices[j] = indices[i] + j - i;
	}
	callback(values(indices, array));
	}

view raw gistfile1.js hosted with ❤ by GitHub

And finally Javascript with Prototype (wow, now like Ruby):

	function generateCombinations(array, r, callback) {
	var n = array.length;
	var indices = $R(0, r, true).toArray();
	var final = $R(n - r, n, true).toArray();
	while (indices.all(function(v, k) {return final[k] == v;})) {
	callback(indices.map(function(k) {return array[k];}));
	var i = r - 1;
	while (indices[i] == n - r + i) i -= 1;
	indices[i] += 1;
	for (var j = i + 1; j < r; j++) indices[j] = indices[i] + j - i;
	}
	callback(indices.map(function(k) {return array[k];}));
	}

view raw gistfile1.js hosted with ❤ by GitHub

Wow, if that doesn't make you want to learn Prototype using Prototype and script.aculo.us: You Never Knew JavaScript Could Do This! then nothing will.

items: choose:

[ combinations ]