Найти все возможные комбинации, которые составляют конкретное число JavaScript

1

Моя проблема: у меня есть число, например, 17; У меня также есть три других постоянных числа: 2, 5, 7;

Мне нужно найти все возможные комбинации, которые составляют конкретное число 17 или любое другое число;

5 + 5 + 7 = 17 (1 combination)
5 + 5 + 5 + 2 = 17 (2 combinations)
2 + 2 + 2 + 2 + 2 + 7 = 17 (3 combinations)
2 + 2 + 2 + 2 + 2 + 2 + 5 = 17 (4 combinations)

Таким образом, ответ: 4. Я создал свой скрипт, который корректно работает с номером 17, но неправильно с большими номерами как 20 или 30. Как заставить его работать со всеми номерами?

const seek = 30;
const firstNum = 2;
const secondNum = 5;
const thirdNum = 7;
let combinations = 0;
const maxDivisor = Math.round(seek / 2);

for (let i = 1; i <= maxDivisor; i += 1) {
    if (secondNum * i + thirdNum === seek) {
        combinations++
    } else if (secondNum * i + firstNum === seek) {
        combinations++
    } else if (firstNum * i + secondNum === seek) {
        combinations++
    } else if (firstNum * i + thirdNum === seek) {
        combinations++
    } else if (thirdNum * i + firstNum === seek || thirdNum * i + secondNum === 0) {
        combinations++
    } else if (firstNum + secondNum + thirdNum === seek) {
        combinations++
    } else if (firstNum * i === seek || thirdNum * i === seek || secondNum * i === seek) {
        combinations++
    }
}
console.log(combinations);
  • 0
    Во второй комбинации у вас сначала 5, а затем 2, а в третьей сначала 2, а затем 7. Итак, вы хотите посчитать: 2 + 5 = 7 и 5 + 2 = 7 как две комбинации?
  • 0
    Это арифметическая модульная задача, называемая линейным диофантовым уравнением. Я предлагаю вам увидеть этот вопрос
Теги:
loops
combinations

4 ответа

1

Простое решение - сначала вычислить максимальные множители для каждого числа и затем суммировать все возможные комбинации.

/** LOGIC **/

function getCombinations(inputNumber, pieceNumbers) {
  const combinations = []
  const initial = maxes(inputNumber, pieceNumbers);
  let divs = initial;
  const sum = createSum(pieceNumbers);
  while (!allZeros(divs)) {
    if (sum(divs) === inputNumber) {
      combinations.push(divs);
    }
    divs = decrement(divs, initial);
  }
  return combinations;
}

/**
 * returns max multiplier for each number
 * that is less than input number
 * ie. for [2, 5] and input 17
 * you get [8 (17 / 2); 3 (17 / 5)]
 */
function maxes(inputNumber, pieceNumbers) {
  return pieceNumbers.map((num, i) =>
    inputNumber / num | 0
  )
}

/**
 * decrements list of numbers till it contains only zeros
 * if we have divs [2, 0] and initial [2, 5] the result
 * will be [1, 5]
 */
function decrement(divs, initial) {
  const arr = divs.slice();
  let i = arr.length;
  while (i--) {
    if (arr[i] > 0) {
      return [...arr.slice(0, i), arr[i] - 1, ...initial.slice(i + 1)];
    }
  }
}

function allZeros(divs) {
  return divs.every(div => div === 0);
} 

function createSum(pieceNumbers) {
  return (divs) => divs.reduce((acc, itm, i) => acc + itm * pieceNumbers[i], 0);
}

function toPrint(combinations, pieceNumbers) {
  const printable = combinations.map(nums =>
    nums.map(
      (n, i) => Array(n).fill(pieceNumbers[i]).join(" + ")
    )
      .filter(x => x)
      .join(" + ")
  ).join("\n");
  return printable;
}

/** VIEW **/

const addPieceEl = document.querySelector(".js-add-piece-number");
const removePieceEl = document.querySelector(".js-remove-piece-number");
const calculateEl  = document.querySelector(".js-calculate");
const displayEl = document.querySelector(".js-display-result");

addPieceEl.addEventListener("click", () => {
  addPieceEl.insertAdjacentHTML("beforebegin", ' <input type="number" class="js-piece-number number" value="7" /> ')
})

removePieceEl.addEventListener("click", () => {
  addPieceEl.previousElementSibling.remove()
})

calculateEl.addEventListener("click", () => {
  const inputNumber = Number(document.querySelector(".js-input-number").value);
  const pieceNumbers = Array.from(document.querySelectorAll(".js-piece-number")).map(el => Number(el.value))
  const combinations = getCombinations(inputNumber, pieceNumbers);
  const total = 'There are ${combinations.length} combinations for ${inputNumber} with ${pieceNumbers.join(", ")}:\n';
  displayEl.textContent = total + toPrint(combinations, pieceNumbers);
});
.number {
width: 30px;
}
Input Number: <input type="number" class="js-input-number number" value="17"/>
<br/>
<br/>
Piece Numbers:
<input type="number" class="js-piece-number number" value="2"/>
<input type="number" class="js-piece-number number" value="5"/>
<input type="number" class="js-piece-number number" value="7"/>
<button class="js-add-piece-number">+</button>
<button class="js-remove-piece-number">-</button>
<br/>
<br/>
<button class="js-calculate">calculate</button>
<pre class="js-display-result"/>
  • 0
    Молодец, я не осознавал, что проблема такая сложная.
0

Я предполагаю, что вам нужны только уникальные решения в том смысле, что 2+5 и 5+2 не уникальны.

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

    const seek = 17;
    const numbs = [2,5,7];
    const minNum = Math.min(...numbs);
    let numberOfCombinations = 0;

    seekCombinations(seek, numbs);

    function seekCombinations (toSeek, numbs) {
        for (let i = 0; i < numbs.length; i++) {
            let newToSeek = toSeek - numbs[i];

            if (newToSeek === 0) { //you found a combination

                numberOfCombinations++;

            } else if (newToSeek >= minNum) { //The new number to seek can still form a combination

                //remove numbers from your list of constants that are smaller then then the number that is already in your current combination so you'll only get unique solutions.
                let index = numbs.indexOf(numbs[i]);
                let newNumbs = numbs.slice(index, numbs.length);

                //recursively call seekCombinations
                seekCombinations (newToSeek, newNumbs, currentCombination)
            }
        }
    }
0

Вы можете проверить все комбинации

const n = 30;
console.log('Number to reach: n = ' + n);

const k = [7, 5, 2];
console.log('Numbers to use: k = ' + k);

console.log('n can be wrote: n = a*k[0] + b*k[1] + c*k[2]');
console.log('Let\ found all combinations of [a, b, c]');
let t = [];
for (let a = 0; n >= a*k[0]; a++)
  for (let b = 0; n >= a*k[0] + b*k[1]; b++)
    for (let c = 0; n >= a*k[0] + b*k[1] + c*k[2]; c++)
      if (n == a*k[0] + b*k[1] + c*k[2])
        t.push([a, b, c]);

console.log('Number of combinations: ' + t.length);
for (let i = 0; i < t.length; i++)
  console.log(
    n + ' = ' + new Array()
    .concat(new Array(t[i][0]).fill(k[0]).join(' + '))
    .concat(new Array(t[i][1]).fill(k[1]).join(' + '))
    .concat(new Array(t[i][2]).fill(k[2]).join(' + '))
    .filter(e => e.length > 0)
    .join(' + ')
  );
-1

так что вопрос? что не так с вашим скриптом или как это сделать?

в случае, если вы его пропустили,

умножая число с i не решает эту проблему. так как:

30 = 2 + 2 + 5 + 7 + 7 + 7
30 = 2 + 2 + 2 + 5 + 5 + 7 + 7

там может появиться любое число из этих трех констант.

эти случаи не охватываются вашим сценарием

  • 0
    извините, я пропустил, мой вопрос был, как это сделать, работая со всеми номерами

Ещё вопросы

Сообщество Overcoder
Наверх
Меню