Combinations in JavaScript

This is a problem that I thought would be trivial at first but turned out to be slightly tricky to implement, so I thought I’d work through it in a blog post.

The idea is to accept a list of lists of options, and return a list of every possible combination of those options. For example:

combinations([
	["a", "b"],
	[1, 2],
]);

// returns

[
	["a", 1],
	["a", 2],
	["b", 1],
	["b", 2],
]

If there were a set number of options lists, this would be straight-forwardly solved with a nested loop:

let carConfigurations = [];

for (let e of engineOptions) {
	for (let t of transmissionOptions) {
		for (let c of colourOptions) {
			carConfigurations.push([e, t, c]);
		}
	}
}

But in our function, we don’t know how many attributes there will be:

function getCombinations(attributes) {
	let combinations = [];
	
	for (let a of attributes[0]) {
		for (let b of attributes[1]) {
			for (let c of attributes[2]) {
				// ...
			}
		}
	}
	
	return combinations;
}

The never-ending nature of this structure brings recursion to mind. Looking at the above loop construction, each successive nested loop is similar to its parent but starting at the next index in the attributes array. So the basic form of a recursive strategy might be to replace the entire inner loop (somehow) with a recursive call, passing the “rest” of the attributes array:

function getCombinations(attributes) {
	let combinations = [];
	
	for (let option of attributes[0]) {
		combinations.push([option, /* ... */]);
	}
	
	return combinations;
}

That’s not quite right, though—when trying to think of what else to put in each combination apart from the current option, I realised that the recursive call will give us a list of combinations, not a list of options. We still need to loop through those combinations, so the function needs two levels of loops:

function getCombinations(attributes) {
	let combinations = [];
	
	for (let option of attributes[0]) {
		let restCombinations = getCombinations(attributes.slice(1));
		
		for (let combination of restCombinations) {
			combinations.push([option, ...combination]);
		}
	}
	
	return combinations;
}

We now need to address some edge cases and the base case—as it stands, this function recurs unconditionally, but will error when it gets to an undefined value beyond the end of attributes.

Assuming the passed attributes is an array containing zero or more arrays of options, there seem to be two base cases to address:

• zero elements
• one element

Taking the zero case first, what should the behaviour be? As a starting point, returning an empty array seems to be a reasonable suggestion. If there are no attributes, there are no combinations. This seems to fit conceptually with how the function works, in that the innermost loop will still be looking at an array, but will do nothing because it has no elements. Let’s add an if for this case at the top:

function getCombinations(attributes) {
	if (attributes.length === 0) {
		return [];
	}
	
	let combinations = [];
	
	for (let option of attributes[0]) {
		let restCombinations = getCombinations(attributes.slice(1));
		
		for (let combination of restCombinations) {
			combinations.push([option, ...combination]);
		}
	}
	
	return combinations;
}

Something I’ve just noticed about the code in this form is that now, the recursive call that sees a one-length attributes list will loop through those options, but then do nothing, as restCombinations will be empty. This means that a one-length attributes list, while arguably an unnecessary case to handle at the top level, will also return an empty array. So we need to handle it explicitly as well.

The behaviour in this case is simple to implement. If there is only one attribute, the possible combinations are just the options for that attribute:

if (attributes.length === 1) {
	return attributes[0].map(option => [option]);
}

Each combination is still represented as an array, in order to keep the data structure consistent.

Putting it all together:

function getCombinations(attributes) {
	if (attributes.length === 0) {
		return [];
	}
	
	if (attributes.length === 1) {
		return attributes[0].map(option => [option]);
	}
	
	let combinations = [];
	
	for (let option of attributes[0]) {
		let restCombinations = getCombinations(attributes.slice(1));
		
		for (let combination of restCombinations) {
			combinations.push([option, ...combination]);
		}
	}
	
	return combinations;
}

After testing this, I realised that we actually don’t need the zero case as long as the top-level call will never receive a zero-length array. This is because the one case never recurs, which is the only time a zero-length slice of the array would have been created:

function getCombinations(attributes) {
	if (attributes.length === 1) {
		return attributes[0].map(option => [option]);
	}
	
	let combinations = [];
	
	for (let option of attributes[0]) {
		let restCombinations = getCombinations(attributes.slice(1));
		
		for (let combination of restCombinations) {
			combinations.push([option, ...combination]);
		}
	}
	
	return combinations;
}

Using more spread syntax—just because it’s cool—and moving the base case into the loop:

function getCombinations(attributes) {
	let [attribute, ...restAttributes] = attributes;
	let combinations = [];
	
	for (let option of attribute) {
		if (restAttributes.length === 0) {
			combinations.push([option]);
		} else {
			let restCombinations = getCombinations(restAttributes);
			
			for (let combination of restCombinations) {
				combinations.push([option, ...combination]);
			}
		}
	}
	
	return combinations;
}