Алгоритм поиска всех возможных массивов максимального размера L, сумма которых равна N или меньше

ProgramBox

Алгоритм поиска всех возможных массивов максимального размера L, сумма которых равна N или меньше

Post author:admin
Запись опубликована:20 марта, 2023
Post category:Вопросы по программированию

#javascript #arrays #algorithm

#javascript #массивы #алгоритм

Вопрос:

Я хочу найти все возможные массивы неотрицательных чисел, сумма которых составляет не более N в JavaScript:

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

Ответ №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 выражение в a 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 resu<
}

// demo
for (let arr of findArrays(2, 4))
    console.log(JSON.stringify(arr));

1. Спасибо! В любом случае мне понадобится некоторая постобработка (поскольку все нули также неприемлемы для меня), поэтому пустые массивы не являются проблемой. Однако эта функция возвращает массивы, сумма maxSize которых равна , not maxSum . У вас где-нибудь опечатка?

2. Действительно, первоначальный вызов recur имел аргумент, которого там не должно быть. Исправлено.

3. теперь это работает! Также мне нравится, как он дает все пустые ответы и ответы со всеми нулями в начале, будет легко обрабатывать после обработки. Я был бы признателен за некоторые объяснения того, насколько это более эффективно, чем мое решение, поскольку я не понимаю, как работает генератор. Но это отвечает на мой вопрос, поэтому я принимаю его. Спасибо!

4. Я добавил к ответу эквивалентную версию без генератора. Я не изучал ваш код подробно, но одна вещь, которая делает его менее эффективным, заключается в том, что он продолжает вычислять сумму подмассивов, в то время как более эффективно просто передавать аргумент, который указывает, сколько значения еще осталось потенциально добавить в массив, не пересекая предел.

5. Хорошая мысль, спасибо. Также мой код слишком быстро заполняет память кучи, поскольку создает больше, чем необходимо массивов. Спасибо за вашу помощь.

Ответ №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 amp;amp; sum > 0) acc.push(value);
      }
      return acc
    }, []
  )
}

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