javascript - 算法:根据一个更改数组的所有值并保持相同的总和

Question

亲爱的，

我遇到了一个必须解决的问题。我是用 JavaScript 来做的，但这通常适用于任何语言，而且更像是一个算法问题。

假设我有一个包含 5 个值的数组，这些值的总和最终应该始终为 500。起始值为 100、100、...、100。

好的，现在我希望在我更改一个值的情况下，其他值以这种方式“调整”，以便保留 500 的“总值”。而且它们不会以某种随机顺序排列，而是保持原来的位置并向平衡方向“移动”，因此它们的原始值保持(一点)。

例子:

100 100 100 100 100

我把第一个设为0结果应该是:

0 125 125 125 125

现在我将秒设置为 0结果应该是:

31.25 0 156.25 156.25 156.25

我有一个工作原型(prototype) - 但我对结果非常不满意。我相信它可以更容易地完成，但我想不出有什么。

我附上我的 JS 源代码及其完整注释。

总体思路如下:

INPUT:
 - array: of N INT elemnt values
 - changed: the index of the element that has been adjusted, this one will be ignored for the array adjustments
 - arrayMin / arrayMax: the values that are considered limits for the array elements
 - arraySum: defines the sum of the array - this is important to see to what SUM the array has to adjust

 PROCESS:
 - the array elements minus 1 (the one that is ignored) are counted
 - the difference made by the one change of the whole sum is computed
 - the difference that has to be made to one and each (except the changed) is computed
 - now there is a loop which adds (or subtracts) the difference to each object
 - if the object reaches its limits (min or max) nothing can be added or subtracted more and this element will be ingored for the rest computation
 - what could not be added to these elements hitting the limit is saved in REST
 - at the end the loop checks if there is any REST and if there is, the loops repeats with REST computed among elements that can and may be adjusted further
 - NOTE: If the rest is really small - treat it

是否有人对我需要它的原因和目的感兴趣 - 我正在考虑使用四个 slider 共享一个“总”值，您可以根据自己的喜好设置它们，其他的则取值取决于变化。

来源: JS source file

**我对想法持开放态度:) **

谢谢

奥利弗

Answer 1

如果没有最小/最大约束，该函数可能如下所示:

function reMapArray(array, changed, arraySum) {
    const sum = array.reduce( (a, b) => a+b );
    const adjust = (sum - arraySum) / (array.length - 1);
    return array.map( (a, i) => i === changed ? a : a - adjust );
}
// Demo use
let array = [100, 100, 100, 100, 100];
array[0] = 0;
array = reMapArray(array, 0, 500);
console.log(array.toString());
array[1] = 0;
array = reMapArray(array, 1, 500);
console.log(array.toString());

添加最小/最大验证后，它可能看起来像这样:

function reMapArray(array, index, minValue, maxValue, arraySum) {
    const sum = array.reduce( (a, b) => a+b );
    if (sum === arraySum) return array; // end recursion: solution found
    const adjust = (arraySum - sum) / array.reduce( 
        // count the values that can still be modified
        (c, a, i) => c + (i === index ? 0 
                        : arraySum > sum ? a < maxValue 
                        : a > minValue), 
        0);
    // apply adjustment, but without getting out of range, and then recurse
    return reMapArray(array.map( (a, i) => 
            i === index ? a : Math.max(minValue, Math.min(maxValue, a + adjust)) ),
        index, minValue, maxValue, arraySum);
}
// Demo use:
let array = [100, 100, 100, 100, 100];
array[0] = 0;
array = reMapArray(array, 0, 0, 150, 500);
console.log(array.toString());
array[1] = 0;
array = reMapArray(array, 1, 0, 150, 500);
console.log(array.toString());

此处的第二个输出与第一个解决方案不同，因为最大值已设置为 150，因此不允许输出 156.25。