26.03.2020, 19:31
|
Новичок на форуме
|
|
Регистрация: 26.03.2020
Сообщений: 2
|
|
Перестановки и разделение массива
Дан массив 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
Поможете решить задачу?
Последний раз редактировалось Pavel_Meridian, 26.03.2020 в 19:33.
|
|
27.03.2020, 13:38
|
Профессор
|
|
Регистрация: 23.09.2014
Сообщений: 197
|
|
const array1 = [1, 2, 3, 4];
const reducer = (accumulator, currentValue) => accumulator + currentValue;
alert(!(array1.reduce(reducer) % 10));
|
|
27.03.2020, 14:12
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,117
|
|
caetus,
как разделить массив на равные суммы?
|
|
27.03.2020, 15:33
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,218
|
|
Как вариант...
Для начала сформировать множество всех перестановок того массива...
Потом каждый элемент этого множества проверять, может ли он быть представлен в виде "одинаковой суммы" с 1-го до i-того и с i+1-го до конца.
Но количество перестановок N элементного множества равно N!
Сообщение от Pavel_Meridian
|
A = [-2, 5, 5, 3, 2, 7]
|
Количество перестановок 720.
|
|
27.03.2020, 15:36
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,218
|
|
Вот пример создания множества всех перестановок N-элементного множества...
https://habr.com/ru/post/276937/
|
|
27.03.2020, 15:40
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,218
|
|
|
|
27.03.2020, 18:36
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,117
|
|
перебор вариантов с бору по сосенке лимит 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>
|
|
28.03.2020, 00:34
|
Новичок на форуме
|
|
Регистрация: 26.03.2020
Сообщений: 2
|
|
Большое спасибо
|
|
|
|