Skip to content

Commit cb14892

Browse files
trekhlebtrekhleb
committed
Add combinations.
1 parent 0af06d6 commit cb14892

16 files changed

Lines changed: 277 additions & 251 deletions

‎README.md‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -32,13 +32,13 @@
3232
* [Fibonacci Number](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci)
3333
* [Cartesian Product](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/cartesian-product)
3434
* [Power Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/power-set)
35-
* [Primality Test](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/primality-test) (trial division)
35+
* [Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/permutations) (with and without repetitions)
36+
* [Combinations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/combinations) (with and without repetitions)
37+
* [Primality Test](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/primality-test) (trial division method)
3638
* [Euclidean Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the greatest common divisor (GCD)
3739
* [Least Common Multiple (LCM)](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple)
3840
* [Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fisher-yates) - random permutation of a finite sequence
3941
* **String**
40-
* [Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/permutations) (with and without repetitions)
41-
* [Combinations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/combinations) (with and without repetitions)
4242
* Minimum Edit distance (Levenshtein Distance)
4343
* Hamming
4444
* Huffman

src/algorithms/string/combinations/README.md renamed to src/algorithms/math/combinations/README.md

File renamed without changes.

src/algorithms/string/combinations/__test__/combineWithRepetitions.test.js renamed to src/algorithms/math/combinations/__test__/combineWithRepetitions.test.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
import combineWithRepetitions from '../combineWithRepetitions';
2-
import factorial from '../../../math/factorial/factorial';
2+
import factorial from '../../factorial/factorial';
33

44
describe('combineWithRepetitions', () => {
55
it('should combine string with repetitions', () => {

‎src/algorithms/math/combinations/__test__/combineWithoutRepetitions.test.js‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
import combineWithoutRepetitions from '../combineWithoutRepetitions';
2+
import factorial from '../../factorial/factorial';
3+
4+
describe('combineWithoutRepetitions', () => {
5+
it('should combine string without repetitions', () => {
6+
expect(combineWithoutRepetitions(['A', 'B'], 3)).toEqual([]);
7+
8+
expect(combineWithoutRepetitions(['A', 'B'], 1)).toEqual([
9+
['A'],
10+
['B'],
11+
]);
12+
13+
expect(combineWithoutRepetitions(['A'], 1)).toEqual([
14+
['A'],
15+
]);
16+
17+
expect(combineWithoutRepetitions(['A', 'B'], 2)).toEqual([
18+
['A', 'B'],
19+
]);
20+
21+
expect(combineWithoutRepetitions(['A', 'B', 'C'], 2)).toEqual([
22+
['A', 'B'],
23+
['A', 'C'],
24+
['B', 'C'],
25+
]);
26+
27+
expect(combineWithoutRepetitions(['A', 'B', 'C'], 3)).toEqual([
28+
['A', 'B', 'C'],
29+
]);
30+
31+
expect(combineWithoutRepetitions(['A', 'B', 'C', 'D'], 3)).toEqual([
32+
['A', 'B', 'C'],
33+
['A', 'B', 'D'],
34+
['A', 'C', 'D'],
35+
['B', 'C', 'D'],
36+
]);
37+
38+
expect(combineWithoutRepetitions(['A', 'B', 'C', 'D', 'E'], 3)).toEqual([
39+
['A', 'B', 'C'],
40+
['A', 'B', 'D'],
41+
['A', 'B', 'E'],
42+
['A', 'C', 'D'],
43+
['A', 'C', 'E'],
44+
['A', 'D', 'E'],
45+
['B', 'C', 'D'],
46+
['B', 'C', 'E'],
47+
['B', 'D', 'E'],
48+
['C', 'D', 'E'],
49+
]);
50+
51+
const combinationOptions = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
52+
const combinationSlotsNumber = 4;
53+
const combinations = combineWithoutRepetitions(combinationOptions, combinationSlotsNumber);
54+
const n = combinationOptions.length;
55+
const r = combinationSlotsNumber;
56+
const expectedNumberOfCombinations = factorial(n) / (factorial(r) * factorial(n - r));
57+
58+
expect(combinations.length).toBe(expectedNumberOfCombinations);
59+
});
60+
});

src/algorithms/string/combinations/combineWithRepetitions.js renamed to src/algorithms/math/combinations/combineWithRepetitions.js

File renamed without changes.

src/algorithms/string/combinations/combineWithoutRepetitions.js renamed to src/algorithms/math/combinations/combineWithoutRepetitions.js

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -38,27 +38,28 @@
3838
*/
3939

4040
/**
41-
* @param {string} combinationOptions
41+
* @param {*[]} combinationOptions
4242
* @param {number} combinationLength
43-
* @return {string[]}
43+
* @return {*[]}
4444
*/
4545
export default function combineWithoutRepetitions(combinationOptions, combinationLength) {
4646
// If combination length is just 1 then return combinationOptions.
4747
if (combinationLength === 1) {
48-
return Array.from(combinationOptions);
48+
return combinationOptions.map(option => [option]);
4949
}
5050

5151
// Init combinations array.
5252
const combinations = [];
5353

5454
for (let i = 0; i <= (combinationOptions.length - combinationLength); i += 1) {
5555
const smallerCombinations = combineWithoutRepetitions(
56-
combinationOptions.substr(i + 1),
56+
combinationOptions.slice(i + 1),
5757
combinationLength - 1,
5858
);
5959

6060
for (let j = 0; j < smallerCombinations.length; j += 1) {
61-
combinations.push(combinationOptions[i] + smallerCombinations[j]);
61+
const combination = [combinationOptions[i]].concat(smallerCombinations[j]);
62+
combinations.push(combination);
6263
}
6364
}
6465

src/algorithms/string/permutations/README.md renamed to src/algorithms/math/permutations/README.md

File renamed without changes.

‎src/algorithms/math/permutations/__test__/permutateWithRepetitions.test.js‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
import permutateWithRepetitions from '../permutateWithRepetitions';
2+
3+
describe('permutateWithRepetitions', () => {
4+
it('should permutate string with repetition', () => {
5+
const permutations0 = permutateWithRepetitions([]);
6+
expect(permutations0).toEqual([]);
7+
8+
const permutations1 = permutateWithRepetitions(['A']);
9+
expect(permutations1).toEqual([
10+
['A'],
11+
]);
12+
13+
const permutations2 = permutateWithRepetitions(['A', 'B']);
14+
expect(permutations2).toEqual([
15+
['A', 'A'],
16+
['A', 'B'],
17+
['B', 'A'],
18+
['B', 'B'],
19+
]);
20+
21+
const permutations3 = permutateWithRepetitions(['A', 'B', 'C']);
22+
expect(permutations3).toEqual([
23+
['A', 'A', 'A'],
24+
['A', 'A', 'B'],
25+
['A', 'A', 'C'],
26+
['A', 'B', 'A'],
27+
['A', 'B', 'B'],
28+
['A', 'B', 'C'],
29+
['A', 'C', 'A'],
30+
['A', 'C', 'B'],
31+
['A', 'C', 'C'],
32+
['B', 'A', 'A'],
33+
['B', 'A', 'B'],
34+
['B', 'A', 'C'],
35+
['B', 'B', 'A'],
36+
['B', 'B', 'B'],
37+
['B', 'B', 'C'],
38+
['B', 'C', 'A'],
39+
['B', 'C', 'B'],
40+
['B', 'C', 'C'],
41+
['C', 'A', 'A'],
42+
['C', 'A', 'B'],
43+
['C', 'A', 'C'],
44+
['C', 'B', 'A'],
45+
['C', 'B', 'B'],
46+
['C', 'B', 'C'],
47+
['C', 'C', 'A'],
48+
['C', 'C', 'B'],
49+
['C', 'C', 'C'],
50+
]);
51+
52+
const permutations4 = permutateWithRepetitions(['A', 'B', 'C', 'D']);
53+
expect(permutations4.length).toBe(4 * 4 * 4 * 4);
54+
});
55+
});

‎src/algorithms/math/permutations/__test__/permutateWithoutRepetitions.test.js‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
import permutateWithoutRepetitions from '../permutateWithoutRepetitions';
2+
import factorial from '../../factorial/factorial';
3+
4+
describe('permutateWithoutRepetitions', () => {
5+
it('should permutate string', () => {
6+
const permutations0 = permutateWithoutRepetitions([]);
7+
expect(permutations0).toEqual([]);
8+
9+
const permutations1 = permutateWithoutRepetitions(['A']);
10+
expect(permutations1).toEqual([
11+
['A'],
12+
]);
13+
14+
const permutations2 = permutateWithoutRepetitions(['A', 'B']);
15+
expect(permutations2.length).toBe(2);
16+
expect(permutations2).toEqual([
17+
['B', 'A'],
18+
['A', 'B'],
19+
]);
20+
21+
const permutations6 = permutateWithoutRepetitions(['A', 'A']);
22+
expect(permutations6.length).toBe(2);
23+
expect(permutations6).toEqual([
24+
['A', 'A'],
25+
['A', 'A'],
26+
]);
27+
28+
const permutations3 = permutateWithoutRepetitions(['A', 'B', 'C']);
29+
expect(permutations3.length).toBe(factorial(3));
30+
expect(permutations3).toEqual([
31+
['C', 'B', 'A'],
32+
['B', 'C', 'A'],
33+
['B', 'A', 'C'],
34+
['C', 'A', 'B'],
35+
['A', 'C', 'B'],
36+
['A', 'B', 'C'],
37+
]);
38+
39+
const permutations4 = permutateWithoutRepetitions(['A', 'B', 'C', 'D']);
40+
expect(permutations4.length).toBe(factorial(4));
41+
expect(permutations4).toEqual([
42+
['D', 'C', 'B', 'A'],
43+
['C', 'D', 'B', 'A'],
44+
['C', 'B', 'D', 'A'],
45+
['C', 'B', 'A', 'D'],
46+
['D', 'B', 'C', 'A'],
47+
['B', 'D', 'C', 'A'],
48+
['B', 'C', 'D', 'A'],
49+
['B', 'C', 'A', 'D'],
50+
['D', 'B', 'A', 'C'],
51+
['B', 'D', 'A', 'C'],
52+
['B', 'A', 'D', 'C'],
53+
['B', 'A', 'C', 'D'],
54+
['D', 'C', 'A', 'B'],
55+
['C', 'D', 'A', 'B'],
56+
['C', 'A', 'D', 'B'],
57+
['C', 'A', 'B', 'D'],
58+
['D', 'A', 'C', 'B'],
59+
['A', 'D', 'C', 'B'],
60+
['A', 'C', 'D', 'B'],
61+
['A', 'C', 'B', 'D'],
62+
['D', 'A', 'B', 'C'],
63+
['A', 'D', 'B', 'C'],
64+
['A', 'B', 'D', 'C'],
65+
['A', 'B', 'C', 'D'],
66+
]);
67+
68+
const permutations5 = permutateWithoutRepetitions(['A', 'B', 'C', 'D', 'E', 'F']);
69+
expect(permutations5.length).toBe(factorial(6));
70+
});
71+
});

‎src/algorithms/math/permutations/permutateWithRepetitions.js‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* @param {*[]} permutationOptions
3+
* @return {*[]}
4+
*/
5+
export default function permutateWithRepetitions(permutationOptions) {
6+
// There is no permutations for empty array.
7+
if (!permutationOptions || permutationOptions.length === 0) {
8+
return [];
9+
}
10+
11+
// There is only one permutation for the 1-element array.
12+
if (permutationOptions.length === 1) {
13+
return [permutationOptions];
14+
}
15+
16+
// Let's create initial set of permutations.
17+
let previousPermutations = permutationOptions.map(option => [option]);
18+
let currentPermutations = [];
19+
let permutationSize = 1;
20+
21+
// While the size of each permutation is less then or equal to options length...
22+
while (permutationSize < permutationOptions.length) {
23+
// Reset all current permutations.
24+
currentPermutations = [];
25+
26+
for (let permIndex = 0; permIndex < previousPermutations.length; permIndex += 1) {
27+
for (let optionIndex = 0; optionIndex < permutationOptions.length; optionIndex += 1) {
28+
let currentPermutation = previousPermutations[permIndex];
29+
currentPermutation = currentPermutation.concat([permutationOptions[optionIndex]]);
30+
currentPermutations.push(currentPermutation);
31+
}
32+
}
33+
34+
// Make current permutations to be the previous ones.
35+
previousPermutations = currentPermutations.slice(0);
36+
37+
// Increase permutation size counter.
38+
permutationSize += 1;
39+
}
40+
41+
return currentPermutations;
42+
}

0 commit comments

Comments
 (0)