-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstring.combinations.js
More file actions
94 lines (76 loc) · 2.13 KB
/
string.combinations.js
File metadata and controls
94 lines (76 loc) · 2.13 KB
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
* @title: String Combinations
* @description: String Combinations
* @author: Thorsten Kober
* @email: [email protected]
*/
// itterative
function combinations(str) {
const result = [];
for (let i = 0; i < str.length; i++) {
const resultLength = result.length;
for (let j = 0; j < resultLength; j++) {
result.push(str[i] + result[j]);
}
result.push(str[i]);
}
return result;
}
// recursive
function combinationsTwo(str) {
const result = [];
function combine(used, unused) {
if (!used && !unused) return;
if (!unused) {
result.push(used);
return;
}
combine(used + unused[0], unused.slice(1));
combine(used, unused.slice(1));
}
combine('', str);
return result;
}
function combinationsThree(str) {
const result = [];
function combine(used, unused, index) {
for (let i = index; i < unused.length; i++) {
used = used + unused[i]; // eslint-disable-line
result.push(used);
combine(used, unused, i + 1);
used = used.substr(0, used.length - 1);
}
}
combine('', str, 0);
return result;
}
// recursive with factorial
// Formula: n! / k!(n- k)!
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
function combinationsCount(n, k) {
let result = 1;
const divisor = (factorial(k) * factorial(n - k));
if (divisor) {
result = factorial(n) / divisor;
}
return result;
}
// npx jest algorithms/string/string.combinations.js
test('combinations()', () => {
const result = ['a', 'ba', 'b', 'ca', 'cba', 'cb', 'c', 'da', 'dba', 'db', 'dca', 'dcba', 'dcb', 'dc', 'd'];
expect(combinations('abcd')).toEqual(result);
});
test('combinationsTwo', () => {
const result = ['abcd', 'abc', 'abd', 'ab', 'acd', 'ac', 'ad', 'a', 'bcd', 'bc', 'bd', 'b', 'cd', 'c', 'd'];
expect(combinationsTwo('abcd')).toEqual(result);
});
test('combinationsThree()', () => {
const result = ['a', 'ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'b', 'bc', 'bcd', 'bd', 'c', 'cd', 'd'];
expect(combinationsThree('abcd')).toEqual(result);
});
test('combinationsCount()', () => {
expect(combinationsCount(4, 2)).toEqual(6);
});