lszk lszk - 7 months ago 27
Javascript Question

add a memoization to recursive algorithm

I have written a function for partitioning a number:

var combinations = function (i) {
var mem = [];
function inner(n, r, m) {
for (var k = m; k <= n; k++) {
if (k == n) {
r.push(k);
mem[r] = 1;

return mem;
}
else {
var copy = r.slice(0);
copy.push(k);
inner(n - k, copy, k);
}
}
}

return inner(i, [], 1);
}


In second step I would like to add a memoization to this algorithm, but can't think of implementing it the right way, beause there is no return statement until the very end (when return is specified e.g. in faactorial or fibbinacci I can add the memoization).
Can anybody drive me to the right direction?

[edit]
I need this algorithm to be as fast as possible. This is a competition for a kata at codewars: link
There is a requirement it must be executed under 6000ms for input up to 330.
That's the best algorithm I can think of, except how to store the partial results.

Answer

Here's a much simpler code that works:

function nr_partitions(n) { return p(n, n); }

function p(sum,largest) {
    if (largest == 0) { return 0; }
    if (sum == 0) { return 1; }
    if (sum < 0) { return 0; }
    return p(sum, largest-1) + p(sum-largest, largest);
}

It uses a well-known recurrence, p(n,k) = p(n,k-1) + p(n-k, k), where p(n.k) denotes the number of partitions of n where the largest part is at most k (e.g. p(3, 2)=2 because we only count 1+1+1,1+2, but not 3). For k=n we get the number of all partitions of n.

Adding memozation involves storing dictionary mapping pairs (sum, largest) to p(sum, largest).