Моя проблема: у меня есть число, например, 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);
Простое решение - сначала вычислить максимальные множители для каждого числа и затем суммировать все возможные комбинации.
/** 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"/>
Я предполагаю, что вам нужны только уникальные решения в том смысле, что 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)
}
}
}
Вы можете проверить все комбинации
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(' + ')
);
так что вопрос? что не так с вашим скриптом или как это сделать?
в случае, если вы его пропустили,
умножая число с i
не решает эту проблему. так как:
30 = 2 + 2 + 5 + 7 + 7 + 7
30 = 2 + 2 + 2 + 5 + 5 + 7 + 7
там может появиться любое число из этих трех констант.
эти случаи не охватываются вашим сценарием
2 + 5 = 7
и5 + 2 = 7
как две комбинации?