为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

12345678_0001 2023-03-18 16:44:27
我想在 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;};
查看完整描述

2 回答

?
眼眸繁星

TA贡献1873条经验 获得超9个赞

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


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));


查看完整回答
反对 回复 2023-03-18
?
萧十郎

TA贡献1815条经验 获得超11个赞

我希望这是有帮助的


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));


查看完整回答
反对 回复 2023-03-18
  • 2 回答
  • 0 关注
  • 79 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信