Перестановки и разделение массива
Дан массив A, и нужно понять можно массив разделить на две части, кажый из которых равен 10 -и или нет.
Например в случае A = [-2, 5, 5, 3, 2, 7] Мы можем иметь эти две подмассивы [-2, 7, 5]и [5, 3, 2]сумма каждой из которых равен 10. Нужно написать функцию которая получает массив и возвращает true или false в зависимости от того разделение массива возможен или нет. function permutDevide(){} console.log(permutDevide([-2, 5, 5, 3, 2, 7])) // true console.log(permutDevide([10, 5, 5])) // true console.log(permutDevide([5, 3, 2, -1])) // false console.log(permutDevide([7, 1, 3, 5, 2, 2])) // true console.log(permutDevide([1, 1, 10, 1, 1, 6])) // true Поможете решить задачу? |
const array1 = [1, 2, 3, 4]; const reducer = (accumulator, currentValue) => accumulator + currentValue; alert(!(array1.reduce(reducer) % 10)); |
caetus,
как разделить массив на равные суммы? |
Как вариант...
Для начала сформировать множество всех перестановок того массива... Потом каждый элемент этого множества проверять, может ли он быть представлен в виде "одинаковой суммы" с 1-го до i-того и с i+1-го до конца. Но количество перестановок N элементного множества равно N! :D Цитата:
|
Вот пример создания множества всех перестановок N-элементного множества...
https://habr.com/ru/post/276937/ |
|
перебор вариантов с бору по сосенке лимит 2 x 10
Pavel_Meridian,
<script> function permute(arr) { var l = arr.length, used = Array(l), data = Array(l); return function* backtracking(pos) { if(pos == l) yield data.slice(); else for(var i=0; i<l; ++i) if(!used[i]) { used[i] = true; data[pos] = arr[i]; yield* backtracking(pos+1); used[i] = false; } }(0); } function permutDevide(arr) { if(arr.reduce((a, b) => a - b, 20)) return false; const gen = permute(arr); let current = gen.next(); while(!current.done) { let temp = [], num = 0; const res = [temp]; for(const elem of current.value) { temp.push(elem); num += elem; if(num == 10) {temp = [], res.push(temp)} } if(res.length == 2) return res; current = gen.next(); } return false } const test = [[-2, 5, 5, 3, 2, 7], [10, 5, 5], [5, 3, 2, -1], [7, 1, 3, 5, 2, 2], [1, 1, 10, 1, 1, 6], [8, 7, 5], [90, 10, -80]]; for(const arr of test) document.write(`${JSON.stringify(arr)} => ${JSON.stringify(permutDevide(arr))}<br>`) </script> |
Большое спасибо
|
Часовой пояс GMT +3, время: 18:21. |