在Javascript或jQuery中计算3个类似大小的组
我们有：
var range = [9,18,3,14,2,6,12,7,11,2,1,4] var total = 89; var group_size = total / 3; 结果我需要3个类似大小的组，但group1和group2永远不会大于group_size。
这个例子的结果是
var group1 = 27; // 9,18 var group2 = 25; // 3,14,2,6 var group3 = 37; // 12,7,11,2,1,4
我怎样才能在Javascript / jQuery中实现这一点？
我想如果你想要这个，你需要用Javascript弹出值。 就像是：
var range = [9,18,3,14,2,6,12,7,11,2,1,4] var total = 89; var group_size = total / 3; var values = [0]; var groupnr = 0; // Reverse the array, because pop will get the last element range = range.reverse(); // While elements while( range.length ) { // get the last element and remove from array var curvalue = range.pop(); // To large, create a new element if( values[groupnr] + curvalue > group_size && groupnr < 2 ) { groupnr++; values[groupnr] = 0; } // Increase values[groupnr] += curvalue; } console.log(values);
更新 ：这确实回答了一个类似的问题（由作者删除），其中不包括前两组不能超过平均值的限制。 有了这个限制，这是一个更简单的问题，而且可能不会引起我的注意。 我在这里留下我的答案，因为它回答的问题似乎在算法上很有趣。
我有一个使用Ramda函数编程库的答案。 你可以在JSFiddle上看到它 。 （请参阅下面的更新版本，不依赖于Ramda。）Ramda提供了许多方便的function，使代码更简单。 如果你已经习惯了函数式编程，那么它们都不会令人惊讶，尽管如果你习惯使用像Underscore或LoDash这样的工具，参数命令可能会倒退。 （相信我，有充分的理由。）
var equalSplit = (function() { var square = function(x) {return x * x;}; var variance = function(groups) { var sizes = map(sum, groups), mean = sum(sizes) / sizes.length; return sum(map(pipe(subtract(mean), square), sizes)); }; var firstGroupChoices = function(group, count) { if (group.length < 2 || count < 2) {return group;} var mean = sum(group) / count; var current = 0, next = group[0], idx = 0; do { current = next; next = next + group[++idx]; } while (next < mean); if (next === mean) { return [group.slice(0, idx + 1)] } else { return [ group.slice(0, idx), group.slice(0, idx + 1) ]; } }; var val = function(group, count, soFar) { if (count <= 0 || group.length == 0) { return {groups: soFar, variance: variance(soFar)}; } if (count == 1) { return val([], 0, soFar.concat([group])); } var choices = firstGroupChoices(group, count); var values = map(function(choice){ return val(group.slice(choice.length), count - 1, soFar.concat([choice])); }, choices); return minWith(function(a, b) { return a.variance - b.variance; }, values); }; return function(group, count) { return val(group, count, []).groups; } }());
以下是小提琴的一些示例输出：
================================================== Input: [9,18,3,14,2,6,12,7,11,2,1,4] Split into 3 groups -------------------------------------------------- Groups: [[9,18,3],[14,2,6,12],[7,11,2,1,4]] Totals: [30,34,25] Variance: 40.66666666666667 ================================================== ================================================== Input: [9,18,3,2,6,12,11,2,4] Split into 3 groups -------------------------------------------------- Groups: [[9,18],[3,2,6,12],[11,2,4]] Totals: [27,23,17] Variance: 50.66666666666667 ================================================== ================================================== Input: [23,10,6,22,22,21,22,14,16,21,13,14,22,16,22,6,16,14,8,20,10,19,12,14,12] Split into 5 groups -------------------------------------------------- Groups: [[23,10,6,22,22],[21,22,14,16],[21,13,14,22],[16,22,6,16,14,8], [20,10,19,12,14,12]] Totals: [83,73,70,82,87] Variance: 206 ==================================================
我完全不相信这个算法会给你一个实际的最优解决方案。 我认为搜索有可能属于局部最小值而不会注意到搜索空间附近山谷中的全局最小值。 但我并没有非常努力地certificate它或提出一个反例。 实际上它也是合理的。 我不知道是否有比这更有效的算法。 这个问题有点像分区问题和背包问题，但我知道我以前从未碰过它。 其中许多问题都是NP Hard / NP Complete，所以我不希望这有一个非常有效的算法。
这个以一种相当简单的递归方式工作。 内部val函数接受一组数字，要创建的组的数量，以及包含到目前为止已创建的所有组的累加器（ soFar ）。 如果count为零，则返回基于累加器的简单结果。 如果count为1，则它以空group重复， count为零，现在包含原始group作为其最后一个元素的累加器。
对于任何其他count它计算剩余组的平均大小，然后选择小于平均值的组的最后一个初始部分和和大于它的第一个（如果有一个完全等于的特殊情况） it），如果这些部分序列在anser中用作组，则重复查找值，然后返回值较小的值。
通过计算形成的每个亚组的总值的方差来确定值。 方差是距平均值的距离的平方和。
例如，如果您从这些值开始：
[8, 6, 7, 5, 3, 1, 9]
并希望将它们分成三组，你会有一个意思
(8 + 6 + 7 + 5 + 3 + 1 + 9 = 39) / 3 => 13
如果你这样打破它们：
[[8, 6], [7, 5, 3], [1, 9]]
你会得到总数
[14, 15, 10]
和方差
(14 - 13)^2 + (15 - 13)^2 + (10 - 13)^2 => 14
但如果你这样打破他们：
[[8, 6], [7, 5], [3, 1, 9]]
你的总数会是
[14, 12, 13]
你的差异就是
[14 - 13)^2 + (12 - 13)^2 + (13 - 13)^2 => 2
而且由于后者的分裂具有较低的方差，因此被认为更好。
例
equalSplit([9, 18, 3, 2, 6, 12, 11, 2, 4], 3 []) = minVal( equalSplit([18, 3, 2, 6, 12, 11, 2, 4], 2, [[9]]), equalSplit([3, 2, 6, 12, 11, 2, 4], 2, [[9, 18]]) ); equalSplit([18, 3, 2, 6, 12, 11, 2, 4], 2, [[9]]) = equalSplit([12, 11, 2, 4], 1, [[9], [18, 3, 2, 6]]); equalSplit([3, 2, 6, 12, 11, 2, 4], 2, [9, 18]) = minVal( equalSplit([12, 11, 2, 4], 1, [[9, 18], [3, 2, 6]]) equalSplit([11, 2, 4], 1, [[9, 18], [3, 2, 6, 12]] ); equalSplit([12, 11, 2, 4], 1, [[9], [18, 3, 2, 6]]) = equalSplit([], 0, [[9], [18, 3, 2, 6], [12, 11, 2, 4]]) equalSplit([12, 11, 2, 4], 1, [[9, 18], [3, 2, 6]]) = equalSplit([], 0, [[9, 18], [3, 2, 6], [12, 11, 2, 4]]) = equalSplit([11, 2, 4], 1, [[9, 18], [3, 2, 6, 12]] equalSplit([], 0, [[9, 18], [3, 2, 6, 12], [11, 2, 4]] equalSplit([], 0, [[9], [18, 3, 2, 6], [12, 11, 2, 4]]) = variance((9), (18 + 3 + 2 + 6), (12 + 11 + 2 + 4)) = variance(9, 29, 29) = 266.67 equalSplit([], 0, [[9, 18], [3, 2, 6], [12, 11, 2, 4]]) = variance((9 + 18), (3 + 2 + 6), (12 + 11 + 2 + 4)) = variance(27, 11, 29) = 194.67 equalSplit([], 0, [[9, 18], [3, 2, 6, 12], [11, 2, 4]] = variance((9 + 18), (3 + 2 + 6 + 12), (11 + 2 + 4)) = variance(27, 23, 17) = 50.67
几乎可以肯定有很多东西可以用来清理这段代码。 但也许这至少是你问题的开始。 这是一个非常有趣的挑战。
更新
我确实创建了一个不依赖于Ramda 的版本 。 代码非常相似。 （我想我真的不需要Ramda，至少不需要最终版本。）：
var equalSplit = (function() { var sum = function(list) {return list.reduce(function(a, b) { return a + b; }, 0);}; var square = function(x) {return x * x;}; var variance = function(groups) { var sizes = groups.map(sum), mean = sum(sizes) / sizes.length; return sum(sizes.map(function(size) { return square(size - mean); }, sizes)); }; var firstGroupChoices = function(group, count) { if (group.length < 2 || count < 2) {return group;} var mean = sum(group) / count; var current = 0, next = group[0], idx = 0; do { current = next; next = next + group[++idx]; } while (next < mean); if (next === mean) { return [group.slice(0, idx + 1)] } else { return [ group.slice(0, idx), group.slice(0, idx + 1) ]; } }; var val = function(group, count, soFar) { if (count <= 0 || group.length == 0) { return {groups: soFar, variance: variance(soFar)}; } if (count == 1) { return val([], 0, soFar.concat([group])); } var choices = firstGroupChoices(group, count); var values = choices.map(function(choice){ return val(group.slice(choice.length), count - 1, soFar.concat([choice])); }); return values.sort(function(a, b) { return a.variance - b.variance; })[0]; }; return function(group, count) { return val(group, count, []).groups; } }());
当然，正如现在在顶部所指出的，这回答了一个与现在被问到的有些不同的问题，但我认为这是一个更有趣的问题！ 🙂