/
SequencesWithSum.js
51 lines (47 loc) · 1.33 KB
/
SequencesWithSum.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
44
45
46
47
48
49
50
51
function factorial(n) {
let prod = 1;
for(let i = 2; i <= n; i++) {
prod *= i;
}
return prod;
}
/**
*
* @param {number} n how many item types
* @param {number} r how many times you selected an item
* @returns {number}
*/
function combinationsWithReplacement(n, r) {
return factorial(n + r - 1) / (factorial(r) * factorial(n - 1));
}
/**
*
* @param {number} numCols how many columns in each sequence
* @param {number} targetSum how many times you selected an item
* @returns {number[][]} 2d array of all non-negative integers sequences with given attributes
*/
function sequencesWithSum(numCols, targetSum) {
const numRows = combinationsWithReplacement(numCols, targetSum);
const vals = [];
vals.push(Array(numCols).fill(0));
vals[0][0] = targetSum;
for(let r = 1; r < numRows; r++) {
vals.push(vals[r - 1].slice());
// optimization of common case
if(vals[r][0] > 0) {
vals[r][0]--;
vals[r][1]++;
}
else {
for(let c = 1; c < numCols; c++) {
if(vals[r][c] > 0) {
vals[r][c] = 0;
vals[r][c + 1] = vals[r - 1][c + 1] + 1;
vals[r][0] = vals[r - 1][c] - 1;
break;
}
}
}
}
return vals;
}