[JavaScript] Getting All Possible Combinations

One of the most interesting mathematical stuff is Combination. A combination is a way of selecting members from a grouping, such that the order of selection does not matter (unlike permutation).

For example, assume that we have 6 balls (numbered from 1 to 6), and a person can select only 4 balls at a time.

Can you write a JavaScript function that can get all the possible 4 ball selections from the available 6 balls?

According to Combination, all the possible 4 ball selections from the 6 balls are (6 Choose 4) which equal to 15. The formula is very simple: n C r = n! / r! n-r!.

Now, let’s use recursion in order to get all the possible combinations.

var Util = function() {
};

Util.getCombinations = function(array, size, start, initialStuff, output) {
    if (initialStuff.length >= size) {
        output.push(initialStuff);
    } else {
        var i;
		
        for (i = start; i < array.length; ++i) {	
	    Util.getCombinations(array, size, i + 1, initialStuff.concat(array[i]), output);
        }
    }
}

Util.getAllPossibleCombinations = function(array, size, output) {
    Util.getCombinations(array, size, 0, [], output);
}

As shown in Util.getAllPossibleCombinations, it takes five parameters as follows:
1. array parameter represents the array of objects that we have.
2. size parameter represents the size of every selection from the array.
3. start parameter represents the current start index.
4. initialStuff parameter represents a temp array that holds every possible combination.
5. output parameter represents the array that holds all the possible arrays of combinations.

In order to know all the possible 4 balls selections from the available 6 balls, you can call the API simply as follows:

// Create an array that holds numbers from 1 ... 6.
var array = [];

for (var i = 1; i <= 6; ++i) {
    array[i - 1] = i;
}

var output = [];

// Select only 4 balls out of the 6 balls at a time ...
Util.getAllPossibleCombinations(array, 4, output);
console.log(output);

In the console, you will find all the possible 15 combinations as follows:

[[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 5, 6], [1, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 5, 6], [2, 4, 5, 6], [3, 4, 5, 6]]
This entry was posted in JavaScript and tagged , , , by Hazem Saleh. Bookmark the permalink.

About Hazem Saleh

Hazem Saleh has more than eleven years of experience in Cloud, Mobile and Open Source technologies. He worked as a software engineer, technical leader, application architect, and technical consultant for many clients around the world. He is an Apache PMC (Project Management Committee) member and a person who spent many years of his life writing open source software. Beside being the author of the "JavaScript Unit Testing" book, "JavaScript Mobile Application Development" book, "Pro JSF and HTML5" book and the co-author of the "Definitive guide to Apache MyFaces" book, Hazem is also an author of many technical articles, a developerWorks contributing author and a technical speaker in both local and international conferences such as ApacheCon North America, Geecon, JavaLand, JSFDays, CON-FESS Vienna and JavaOne. Hazem is an XIBMer, he worked in IBM for ten years. Now, He is working for Nickelodeon New York as a Mobile Architect. He is also an OpenGroup Master Certified Specialist.