[JavaScript] Getting All Possible Permutations

One of the most interesting mathematical stuff is Permutation. A permutation is the act of re-arranging all the members of a set into some sequence or order, such that the order of selection always matters (unlike combination).

Assume that we have 3 balls (Red, Green and Blue). If we want all the possible permutation then we will have the following 6 possible permutation:

  • Red, Green, Blue.
  • Red, Blue, Green.
  • Green, Blue, Red.
  • Green, Red, Blue.
  • Blue, Red, Green.
  • Blue, Green, Red.

Mathematically, the number of permutations of n distinct objects is n factorial usually written as n!. Now, let’s write a simple function in JavaScript that gets the unique permutation for a set of objects.

var Util = function() {
};

Util.getPermuts = function(array, start, output) {
	if (start >= array.length) {
		var arr = array.slice(0); //clone the array		
		output.push(arr);
	} else {
		var i;
		
		for (i = start; i < array.length; ++i) {
			Util.swap(array, start, i);	
			Util.getPermuts(array, start + 1, output);	
			Util.swap(array, start, i);	
		}
	}
}

Util.getAllPossiblePermuts = function(array, output) {
	Util.getPermuts(array, 0, output);
}

Util.swap = function(array, from, to) {
	var tmp = array[from];
	array[from] = array[to];
	array[to] = tmp;
}

// Test API ...
var array = ['R', 'G', 'B'];
var output = [];

Util.getAllPossiblePermuts(array, output);
console.log(output);

As shown in Util.getPermuts, it takes three parameters as follows:
1. array parameter represents the array of objects that we have.
2. start parameter represents the current start index.
3. output parameter represents the array that holds all the possible arrays of permutations.

Util.getPermuts recursively swaps the array elements in order to get all the possible permutations of the input array.

The previous code covers permutation without repetition which means that we use every element that we have only once in every possible permutation.

What about if we want to get all the possible permutations with repetition. Assume that we have 4 blank papers and we would like to paint them with all the possible ways using Red, Green and Blue colors.

Can you write a JavaScript function that can get all the possible 4 papers’ paintings?

According to Permutation with repetition, all the possible 4 papers’ paintings with 3 colors can be calculated as (3 power 4) which equal to 81. The formula is very simple: n P(with repetition) r = n ^ k.

Now, let’s use recursion in order to get all the possible permutation with repetition.

var Util = function() {
};

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

Util.getAllPossibleRPermuts = function(array, size, output) {
	Util.getRPermuts(array, size, [], output);
}

As shown in Util.getRPermuts, it takes four parameters as follows:
1. array parameter represents the array of objects (colors in our case) that we have.
2. size parameter represents the size of every permutation item.
3. initialStuff parameter represents a temp array that holds every possible permutation with repetition.
4. output parameter represents the array that holds all the possible arrays of permutation with repetition.

In order to know all the possible 4 papers’ paintings using the available 3 colors, you can call the permutation with repetition API simply as follows:

// Create the array of the possible 3 colors ...
var possibleColors = ['R', 'G', 'B'];
var output = [];
var papersNo = 4;

// get all the possible painting for the 4 papers that we have.
Util.getAllPossibleRPermuts(possibleColors, papersNo, output);
console.log(output);

In the console, you will find all the possible 81 permutation with repetition as follows:

[["R", "R", "R", "R"], ["R", "R", "R", "G"], ["R", "R", "R", "B"], ["R", "R", "G", "R"], ["R", "R", "G", "G"], ["R", "R", "G", "B"], ["R", "R", "B", "R"], ["R", "R", "B", "G"], ["R", "R", "B", "B"], ["R", "G", "R", "R"], ["R", "G", "R", "G"], ["R", "G", "R", "B"], ["R", "G", "G", "R"], ["R", "G", "G", "G"], ["R", "G", "G", "B"], ["R", "G", "B", "R"], ["R", "G", "B", "G"], ["R", "G", "B", "B"], ["R", "B", "R", "R"], ["R", "B", "R", "G"], ["R", "B", "R", "B"], ["R", "B", "G", "R"], ["R", "B", "G", "G"], ["R", "B", "G", "B"], ["R", "B", "B", "R"], ["R", "B", "B", "G"], ["R", "B", "B", "B"], ["G", "R", "R", "R"], ["G", "R", "R", "G"], ["G", "R", "R", "B"], ["G", "R", "G", "R"], ["G", "R", "G", "G"], ["G", "R", "G", "B"], ["G", "R", "B", "R"], ["G", "R", "B", "G"], ["G", "R", "B", "B"], ["G", "G", "R", "R"], ["G", "G", "R", "G"], ["G", "G", "R", "B"], ["G", "G", "G", "R"], ["G", "G", "G", "G"], ["G", "G", "G", "B"], ["G", "G", "B", "R"], ["G", "G", "B", "G"], ["G", "G", "B", "B"], ["G", "B", "R", "R"], ["G", "B", "R", "G"], ["G", "B", "R", "B"], ["G", "B", "G", "R"], ["G", "B", "G", "G"], ["G", "B", "G", "B"], ["G", "B", "B", "R"], ["G", "B", "B", "G"], ["G", "B", "B", "B"], ["B", "R", "R", "R"], ["B", "R", "R", "G"], ["B", "R", "R", "B"], ["B", "R", "G", "R"], ["B", "R", "G", "G"], ["B", "R", "G", "B"], ["B", "R", "B", "R"], ["B", "R", "B", "G"], ["B", "R", "B", "B"], ["B", "G", "R", "R"], ["B", "G", "R", "G"], ["B", "G", "R", "B"], ["B", "G", "G", "R"], ["B", "G", "G", "G"], ["B", "G", "G", "B"], ["B", "G", "B", "R"], ["B", "G", "B", "G"], ["B", "G", "B", "B"], ["B", "B", "R", "R"], ["B", "B", "R", "G"], ["B", "B", "R", "B"], ["B", "B", "G", "R"], ["B", "B", "G", "G"], ["B", "B", "G", "B"], ["B", "B", "B", "R"], ["B", "B", "B", "G"], ["B", "B", "B", "B"]]

[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]]