查找总和为 N 或更小的最大大小 L 的所有可能数组的算法

Question

我想在 JavaScript 中找到所有可能的数组 - 非负数 - 总和 - 至多 - N：

function findArrays(maxSize, maxSum){}

输入示例： findArrays(3, 10)

一些可接受的输出：（不写全部，因为它太长了）

[[0], [0,0,0], [10,0,0], [1,9], [1,2,3] /*, ... */]

到目前为止我尝试了什么：

我知道它看起来像家庭作业，但它不是 :) 我可以想到一个解决方案，它只生成所有 ( size*maxSum) 个可接受大小的可能数组，然后遍历它们以检查总和是否大于maxSum。但是，我认为随着变大，这种解决方案在性能方面非常糟糕maxSum。我正在寻找更有效的实施，但我不知道从哪里开始。

我的“坏”解决方案

function getNextArray(r,maxVal){

    for(var i=r.length-1;i>=0;i--){

        if(r[i]<maxVal){

            r[i]++;

            if(i<r.length-1){

                r[i+1]=0;

            }

            break;

        }

    }

    return r;

}

function getAllArraysOfSize(size, maxVal){

    var arrays=[],r=[],i;

    for(i=0;i<size;i++){

        r[i]=0;

    }

    while(r.reduce((a, b) => a + b, 0) < (maxVal*size)){

        r = getNextArray(r.slice(),maxVal);

        arrays.push(r);

    }

    return arrays;

};

function findArrays(maxSize, maxSum){

    var allArrays=[],arraysOfFixedSize=[],acceptableArrays=[],i,j;

    for(i=1; i<=maxSize; i++){

        arraysOfFixedSize=getAllArraysOfSize(i,maxSum);

        for(j=0; j<arraysOfFixedSize.length; j++){

            allArrays.push(arraysOfFixedSize[j]);

        }

    }

    for(i=0; i<allArrays.length; i++){

        if(allArrays[i].reduce((a, b) => a + b, 0) <= maxSum){

            acceptableArrays.push(allArrays[i]);

        }

    }

    return acceptableArrays;

};

Answer 1

您可以使用递归和生成器。对于更高价值的参数，输出的数量会快速增长，所以我在这里将它们保持在较低水平：

function * findArrays(maxSize, maxSum) {

  let arr = [];

  

  function * recur(maxSum) {

    let k = arr.length;

    yield [...arr]; // or: if (k) yield [...arr]

    if (k === maxSize) return;

    for (let i = 0; i <= maxSum; i++) {

      arr[k] = i;

      yield * recur(maxSum - i);

    }

    arr.length = k;

  }

  

  yield * recur(maxSum);  

}

// demo

for (let arr of findArrays(2, 4))

    console.log(JSON.stringify(arr));

注意：这也会产生空数组，这是有道理的。如果你想避免这种情况，那么只需检查你不会产生一个空数组。

如果您更喜欢使用普通函数而不是生成器，则将最里面的yield表达式转换为push数组result，如下所示：

function findArrays(maxSize, maxSum) {

  let arr = [];

  let result = []; // <--- will collect all the subarrays

 

  function recur(maxSum) {

    let k = arr.length;

    result.push([...arr]);

    if (k === maxSize) return;

    for (let i = 0; i <= maxSum; i++) {

      arr[k] = i;

      recur(maxSum - i);

    }

    arr.length = k;

  }

  

  recur(maxSum);

  return result;

}

// demo

for (let arr of findArrays(2, 4))

    console.log(JSON.stringify(arr));

Answer 2

我希望这是有帮助的

const data = [[0],[0,0,0],[10,0,0],[1,9],[1,2,3]];

function findArrays(maxSize, maxSum){

  return data.reduce(

    (acc, value) => {

      if (value.length <= maxSize) {

        const tempValue = value;

        const sum = tempValue.reduce((acc, val) => val >= 0 ? acc + val : 0, 0);

        if (sum <= maxSum && sum > 0) acc.push(value);

      }

      return acc

    }, []

  )

}

console.log(findArrays(3, 10));