javascript - 找到 n 个参数的所有可能组合(正负)总和？

Question

我正在尝试构建一个接受可变数量参数的函数。

该函数接受 n 个输入并计算所有可能的加法和减法的和，例如如果参数是 1,2,3

1 + 2 + 3
1 - 2 - 3
1 + 2 - 3
1 - 2 + 3

最后，该函数输出最接近零的和。在这种情况下，答案仅为 0。

在弄清楚如何循环 n 个参数以使用 + 和 - 运算符的所有可能组合时，我遇到了很多问题。

我已经成功地构建了一个函数，可以添加所有变量或减去所有变量，但我一直在研究如何处理各种 + 和 - ，尤其是在考虑多个可能的变量时。

var sub = 0;
var add = 0;

function sumAll() {
  var i;

  for (i = 0; i < arguments.length; i++) {
    sub -= arguments[i];
  }
  for (i = 0; i < arguments.length; i++) {
    add += arguments[i];
  }
  return add;
  return sub;
};
console.log(add, sub); // just to test the outputs

我想为任何给定数量的输入(总是整数，正数和负数)计算所有可能的 + 和 - 排列。欢迎提出将总和与零进行比较的建议，尽管我还没有尝试过，并且宁愿在询问该部分之前先尝试一下。谢谢。

Answer 1

我会遍历一个数字的可能的位。例如，如果有 3 个参数，则有 3 个位，这些位可表示的最高数字是 2 ** 3 - 1 , 或 7(当设置所有 3 位时，111 或 1+2+4)。然后，从0迭代到7，检查每个位索引是否设置。

例如，在第一次迭代中，当数字为 0 时，位为 000 , 对应于 +++ - 将所有 3 个参数相加。

在第二次迭代中，当数字为 1 时，位为 001 , 对应于 -++ ，所以减去第一个参数，并添加其他两个参数。

第三次迭代将有 2 , 或 010 , 或 +-+ .

第三次迭代将有 3 , 或 011 , 或 +-- .

第三次迭代将有 4 , 或 100 , 或 -++ .

继续该模式直到结束，同时跟踪到目前为止最接近零的总数。

如果需要，您也可以在发现小计为 0 时立即返回。

const sumAll = (...args) => {
  const limit = 2 ** args.length - 1; // eg, 2 ** 3 - 1 = 7
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    // eg '000', or '001', or '010', or '011', or '100', etc
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    console.log('i:', i, 'bitStr:', bitStr);
    args.forEach((arg, bitPos) => {
      if (bitStr[args.length - 1 - bitPos] === '0') {
        console.log('+', arg);
        subtotal += arg;
      } else {
        console.log('-', arg);
        subtotal -= arg;
      }
    });
    console.log('subtotal', subtotal);
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

您可以通过替换 [args.length - 1 - bitPos] 来“简化”与 [bitPos]对于相同的结果，但它看起来会更困惑 - 例如 3 ( 011 或 +-- )，将变为 110 (--+)。

如果没有所有证明代码按预期工作的日志，它会更短:

const sumAll = (...args) => {
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = 0;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));

您可以通过任意选择第一个数字的符号来将操作次数减半。例如。目前，sumAll(9, 1) , 都是 8 的答案( 9 - 1 ) 和 -8 ( 1 - 9 ) 是有效的，因为它们都同样接近于 0。无论输入如何，如果 +-产生一个最接近 0 的数字，然后是 -+也一样，只是符号相反。同样，如果 ++---产生一个最接近 0 的数字，然后是 --+++也一样，符号相反。通过为第一个数字选择一个符号，您可能会强制计算结果只有一个一个符号，但这不会影响算法结果与 0 的距离。

改进不大(例如，10 个参数，2 ** 10 - 1 -> 1023 次迭代改进为 2 ** 9 - 1 -> 511 次迭代)，但确实不错。

const sumAll = (...args) => {
  let initialDigit = args.shift();
  const limit = 2 **  args.length - 1;
  let totalClosestToZeroSoFar = Infinity;
  for (let i = 0; i < limit; i++) {
    const bitStr = i.toString(2).padStart(args.length, '0');
    let subtotal = initialDigit;
    args.forEach((arg, bitPos) => {
      subtotal += (bitStr[bitPos] === '0' ? -1 : 1) * arg;
    });
    if (Math.abs(subtotal) < Math.abs(totalClosestToZeroSoFar)) {
      totalClosestToZeroSoFar = subtotal;
    }
  }
  return totalClosestToZeroSoFar;
};

console.log('final', sumAll(1, 2, 3));