查找所有最大大小为L或等于N的数组的算法 [英] Algorithm to find all possible arrays of max size L that sum up to N or less

问题描述

我想找到所有可能的数组-非负数-在JavaScript中最多等于-N-

I want to find all possible arrays -of non-negative numbers- that sum up to -at most- N in JavaScript:

function findArrays(maxSize, maxSum){}

示例输入： findArrays （3，10）

一些可接受的输出结果：（不要写太多，因为太长了）

Some acceptable outputs: (not writing all as it would be too long)

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

到目前为止我尝试过的事情：

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

I know it looks like homework but it's not :) I can think of a solution that simply generates all (size*maxSum) possible arrays of acceptable sizes and then iterate through them to check if sum is greater than maxSum. However, I think this solution is very bad in terms of performance as maxSum gets bigger. I'm looking for a more efficient implementation but I just don't know where to start.

我的糟糕消息是解决方案

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

推荐答案

您可以使用递归和生成器。对于值较高的参数，输出数量迅速增加，因此在这里将其保持在较低水平：

You can use recursion and a generator. The number of outputs grows quickly for higher valued arguments, so I keep them low here:

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

NB：这也会产生空数组，这很有意义。如果要避免这种情况，只需检查一下是否不会产生空数组即可。

NB: this also produces the empty array, which makes sense. If you want to avoid this, then just check that you don't yield an empty array.

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

If you prefer working with plain functions instead of generators, then translate the innermost yield expression to a push unto a result array, as follows:

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

这篇关于查找所有最大大小为L或等于N的数组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！