# Recursive implementation of integer partition without re-arrangement

Problem: Integer partition without re-arrangement

Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an integer k.

Output: The largest job from partitioning S into k or fewer ranges, to minimize the maximum sum over all the ranges, without reordering any of the numbers. Also the indexes of the partition dividers.

'use strict';

var sum = function(p, c) {
return p + c;
};

var integerPartitionRec = function(n, k, S, divider_indexes) {
if (divider_indexes === undefined) divider_indexes = [];
if (i === 1) return [S[0], divider_indexes];
if (k === 1) return [S.slice(0, n).reduce(sum), divider_indexes];

var cost, prefix, min_cost = Number.MAX_VALUE,
min_divider_indexes = [];
for (var i = 1; i < n; i++) {
prefix = integerPartitionRec(i, k - 1, S, divider_indexes.concat(i));
cost = Math.max(prefix[0], S.slice(i, n).reduce(sum));
if (cost < min_cost) {
min_cost = cost;
min_divider_indexes = prefix[1];
}
}

return [min_cost, min_divider_indexes];
};

// define M[n,k] to be the minimum possible cost over all partitionings of {s1 , . . . , sn }
// into k ranges, where the cost of a partition is the largest sum of elements in one of its parts.
// O(kn^2) time

var integerPartitionDp = function(S, k) {
var n = S.length;
var cache = [
[0]
];

/* Dividers */
var d = []

/* Prefix Sums */
var p = [0];

for (var i = 1; i <= n; i++) {
p[i] = p[i - 1] + S[i - 1];
}

for (i = 1; i <= n; i++) {
cache[i] = [0, p[i]];
}

for (var j = 1; j <= k; j++) {
cache[0][j] = 0
cache[1][j] = S[0];
}

for (i = 2; i <= n; i++) {
for (j = 2; j <= k; j++) {
cache[i][j] = Number.MAX_VALUE;

var cost;
for (var x = 1; x < i; x++) {
cost = Math.max(cache[x][j - 1], p[i] - p[x]);
if (cost < cache[i][j]) {
cache[i][j] = cost;
if (d[i] === undefined) d[i] = [];
d[i][j] = x;
}
}
}
}

var dividers = [];
var curr = d[n][k];
var count = k;
while (curr !== undefined) {
dividers.push(curr);
curr = d[curr] ? d[curr][--count]: undefined;
}

return [cache[n][k], dividers];
}

var run = function() {
var test = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log('S', test);

console.log(integerPartitionRec(test.length, 3, test));
console.log(integerPartitionDp(test, 3));
};

run();

• Should we understand that integerPartitionRec and integerPartitionDp do essentially the same thing and that you want both reviewed? – Peter Taylor May 1 '18 at 14:48