-
Notifications
You must be signed in to change notification settings - Fork 224
/
combinations_replacement.js
43 lines (39 loc) · 1.78 KB
/
combinations_replacement.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* Implementation of [Combinations](https://en.wikipedia.org/wiki/Combination) with replacement
* Combinations are unique subsets of a collection - in this case, k x from a collection at a time.
* 'With replacement' means that a given element can be chosen multiple times.
* Unlike permutation, order doesn't matter for combinations.
*
* @param {Array} x any type of data
* @param {int} k the number of objects in each group (without replacement)
* @returns {Array<Array>} array of permutations
* @example
* combinationsReplacement([1, 2], 2); // => [[1, 1], [1, 2], [2, 2]]
*/
function combinationsReplacement(x, k) {
const combinationList = [];
for (let i = 0; i < x.length; i++) {
if (k === 1) {
// If we're requested to find only one element, we don't need
// to recurse: just push `x[i]` onto the list of combinations.
combinationList.push([x[i]]);
} else {
// Otherwise, recursively find combinations, given `k - 1`. Note that
// we request `k - 1`, so if you were looking for k=3 combinations, we're
// requesting k=2. This -1 gets reversed in the for loop right after this
// code, since we concatenate `x[i]` onto the selected combinations,
// bringing `k` back up to your requested level.
// This recursion may go many levels deep, since it only stops once
// k=1.
const subsetCombinations = combinationsReplacement(
x.slice(i, x.length),
k - 1
);
for (let j = 0; j < subsetCombinations.length; j++) {
combinationList.push([x[i]].concat(subsetCombinations[j]));
}
}
}
return combinationList;
}
export default combinationsReplacement;