将 JavaScript 或 Python 中的数组重新调整为特定的最大值和目标总和

Question

我正在使用 JavaScript（但也可以是 Python）处理数据集，并且需要一些关于数学缩放问题的帮助。我想转换数组的值，以便新数组符合两个约束：

1. newMax

   ：新数组的最大值应等于指定值。

2. newSum

   ：新数组中所有元素的总和应等于指定值。

变换应尽可能保持原始值的相对比例。

给出：

• 正值数组

  original

  。

• newMax

  和

  newSum

  的值。

必填：

• 一个 JavaScript 函数，它基于

  modified

  创建新数组

  original

  ，并使用指定的

  newMax

  和

  newSum

  。

function rescaleArray(original, newMax, newSum) {
  // Algorithm to be determined
}

// Example of usage
let original = [/* ...array of values... */];
let newMax = 48; // desired maximum value in the new array
let newSum = 68387; // desired sum of values in the new array

let modified = rescaleArray(original, newMax, newSum);

如何解决这个问题以找到合适的转换？我专门寻找一种适用于数组的有效算法或方法。

我尝试过的：

我尝试了很多算法，包括下面的算法，但我只能达到最大值或总和，而不能同时达到两者。我也尝试过线性规划但没有成功。下面的示例可以达到最大值，但不能达到总和。

function rescaleArray(original, newMax, newSum) {
    let modified = original.slice();
    let currentMax = Math.max(...modified);
    let currentSum = modified.reduce((a, b) => a + b, 0);
  
    // First scale up/down to the new max
    let scaleToMaxFactor = newMax / currentMax;
    modified = modified.map(value => value * scaleToMaxFactor);

    // Now adjust the sum
    let iterativeScaleFactor = newSum / modified.reduce((a, b) => a + b, 0);

    let tolerance = 0.0001; // Define a tolerance level to avoid infinite loop
    let diff = Math.abs(newSum - currentSum);

    while (diff > tolerance) {
        modified = modified.map(value => value * iterativeScaleFactor);
        currentSum = modified.reduce((a, b) => a + b, 0);
        iterativeScaleFactor = newSum / currentSum;

        // prevent endless loop in case it is not converging
        let newDiff = Math.abs(newSum - currentSum);
        if (newDiff >= diff) {
          break; // the difference is not reducing anymore, break out
        }
        diff = newDiff;
    }

    // Final check to ensure the max is within the tolerance
    currentMax = Math.max(...modified);
    if (Math.abs(currentMax - newMax) > tolerance) {
        // Adjust for new Max again, if required
        scaleToMaxFactor = newMax / currentMax;
        modified = modified.map(value => value * scaleToMaxFactor);
    }

    return modified;
}

Answer 1

如果结果值可以是浮点数，那么您可以使用线性投影。

您将在下面的代码中找到公式以及运行示例：

const sum = (arr) => arr.reduce((a, b) => a + b, 0);
const max = (arr) => Math.max(...arr);

function rescaleArray(original, newMax, newSum) {
    const n = original.length;
    const currentMax = max(original);
    const currentSum = sum(original);
    
    const coefficient = (newSum - n * newMax) / (currentSum - n * currentMax);
    const constant = newMax - coefficient * currentMax;
    
    return original.map(value => coefficient * value + constant);
}

// Example run
const a = [110, 30, 71, 114, 28, 23, 96];
const b = rescaleArray(a, 200, 700);
console.log("max", max(b));
console.log("sum", sum(b));
console.log(b);

没有检查是否确实有解决方案。

如果输入数组中的所有值都相等，则

coefficient

公式将除以零。当发生这种情况时，输出将包含

NaN

值。

即使所有数组值都等于新的最大值，也可能是所需的总和太大。在这种情况下，仍然可以达到所需的总和，但给定的

newMax

实际上将是结果数组的 minimum。

当值必须为非负数时

对于某些输入，结果数组中的值可能为负数。

我们可以使用以下方法：

• 从此结果中删除最大值
• 应用类似的算法来获取新数组，但这次具有所需的最小值，并给出原始目标作为目标总和，但删除了最大值（正如我们在上一步中删除的那样）
• 将删除的最大值注入回结果中。

看起来是这样的：

const sum = (arr) => arr.reduce((a, b) => a + b, 0);
const max = (arr) => Math.max(...arr);
const min = (arr) => Math.min(...arr);

function rescaleArrayHelper(original, extreme, newExtr, newSum) {
    const n = original.length;
    const currentExtr = extreme(original);
    const currentSum = sum(original);

    const coefficient = (newSum - n * newExtr) / (currentSum - n * currentExtr);
    const constant = newExtr - coefficient * currentExtr;

    return original.map(value => coefficient * value + constant);
}

function rescaleArray(original, newMax, newSum) {
    const result = rescaleArrayHelper(original, max, newMax, newSum);
    if (min(result) >= 0) return result;
    newMax = max(result); // Re-getting it, to avoid floating point imprecission issues
    let i = result.indexOf(newMax);
    result.splice(i, 1); // Remove that maximum temporarily
    const result2 = rescaleArrayHelper(original, min, 0, newSum - newMax);
    result2.splice(i, 0, newMax); // Re-insert
    return result2;
}

// Example run
const a = [110, 30, 71, 114, 28, 23, 96];
const b = rescaleArray(a, 200, 500);
console.log("max", max(b));
console.log("sum", sum(b));
console.log(b);