Permutation & Combination
Paimpol Le Fanny Crossfield, Paul Signac
1. Permutation
1.1 What is Permutation?
A permutation is the choice of r things from a set of n things without replacement and where the order matters.
It is denoted by \(_nP_r\).
\[_nP_r=\frac{n!}{(n-r)!}\]
1.2 Permutation Implementation
A Permutation can be implemented using a recursive function in the manner shown in the figure below.
3-letter word permutations that can be made with X, Y, and Z
// title:'Permutation.js'
const getPermutations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// When selecting one out of n (nP1), immediately return the elements of all arrays. Since there is only one choice, the order is meaningless.
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
// Arrays other than the corresponding fixed
const permutations = getPermutations(rest, selectNumber - 1);
// Get the permutation for the remainder.
const attached = permutations.map((el) => [fixed, ...el]);
// attach fixed value to returned permutation
results.push(...attached);
// push everything with array spread syntax
});
return results; // results return with results
}
2. Combination
2.1 What is Combination?
A Combination is the choice of r things from a set of n things without replacement and where the order does not matter.
It is denoted by \(_nC_r\).
\[_nC_r=\frac{_nP_r}{r!}=\frac{n!}{r!(n-r)!}\]
2.2 Combination Implementation
A Combination can be implemented using a recursive function in the manner shown in the figure below.
Combination to choose 3 out of ABCDE
// title:'Combination.js'
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// When selecting one out of n (nC1), immediately return all array elements
arr.forEach((fixed, index, origin) => {
const rest = origin. slice(index + 1);
// After everything except the corresponding fixed
const combinations = getCombinations(rest, selectNumber - 1);
// Find the combination for the remainder.
const attached = combinations.map((el) => [fixed, ...el]);
// Attach a fixed value to the returned combination
results.push(...attached);
// push everything with array spread syntax
});
return results; // results return with results
}