Задача
Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых равна 10.
С первого взгляда, задача простая, всего то надо написать рекурсию и перебрать все значения.
Или можно использовать двоичный инкремент но для того чтобы перебрать все значения для вектора чисел длинной N, потребуется 2^n итераций.
Для начала выберем частный случай, предположим что массив состоит из чисел > 0. Позже на основе этого примера мы реализуем все случаи
ШАГ 1
а) Рассмотрим один из частных случаев — сумма всех элементов массива < 10.
Логика проста, sum(V) < 10, то sum(V)-V[i] < sum, то есть если сумма комбинаций всегда будет меньше 10.
б) Если sum(V) = 10, то сумма sum(V)-V[i] < sum. Результат будет только один V.
ШАГ 2
Удаляем из вектора все лишнее
Как пример возьмем массив [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2 ,2, 2, 1, 5, 5, 5].
В нем сразу видно что нет смысла искать комбинации если значение > 10, но все станет сразу понятно. если мы его отсортируем:
[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20]
На данном этапе мы можем уже точно знаем что надо удалить все элементы больше 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]
Но на самом деле все немного интереснее. нам нужно ограничить вектор, до того значения чтобы V[0]+V[i] <= 10; где i стремиться к N; Но если V[i] = 10, то в результат мы добавляем 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]
ШАГ 3
В уже отфильтрованном массиве существуют повторяющиеся элементы. Если разложить вектор на под вектора, и посчитать их сумму, то получим что то вроде этого
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[ 5, 5, 5, 5] => 20
[ 8, 8, 8] => 24
[ 9,9] => 18
Суть моих размышлений такая, что не имеет смысл рассматривать комбинации из повторяющихся чисел, если их количество*значение > 10. То есть обрезаем под вектора до того момента, чтобы их сумма была меньше 10, а те что равны 10 добавляем в результат:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[ 5, 5, 5, 5] => [5]
[ 8, 8, 8] => [8]
[ 9,9] => [9]
В результате 3 го шага, наш вектор будет следующим
[1, 1, 2, 2, 2, 4, 5, 8, 9]
Как видим размер вектора нас сократился, с 25 до 9, это намного меньше (помним про количество итераций);
С отрицательными числами
Тут немного сложнее. будем предполагать что мы реализовали функцию нахождения комбинаций для положительного отсортированного вектора иcходя из предыдущих ограничений.
comb(arr,sum), где sum — необходимая сумма, arr — вектор отсортированный из положительных чисел
Для примера возьмем вектор:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12, -10, 9]
1. Разбиваем вектор
A = только положительные значения
B = только отрицательные значения
А также смотрим есть ли у нас значения = 0
2. Сортировка
Сортируем вектора (положительные по возрастанию, отрицательные по убыванию)
Проверяем частные случай для положительных чисел (ШАГ 1)
3. Проверка положительных
Проверяем для положительных значений
comb(B,10)
3. Проверка для отрицательных
создаем комбинации из всех отрицательных числе, но с ограничением:
(сумма элементов по модулю) < (сумма всех положительных) + 10
находим комбинации для НОВОЙ эталонной сумм ( сумма элементов по модулю + 10)
4. Равенство 0
Если в исходном векторе есть значение 0, то к результату добавляем все сочетания + 0;
В результате таких вот ограничений, в среднем при тестировании значений с массивом длинной 28 и 1000 тестов, выигрыш по времени почти 42%
function combine(arr, etalon = 10) { //--------------------------------------------// //------------- helpers --------------------// // Создание бинарного вектора // Create binnary array function createBin(length) { let bin = []; for (let i = 0; i < length; i++) { bin[i] = false; } return bin; } //Бинарное увеличение на 1 //Binnary add 1 bit function binAddBit(bin, i = 0) { if (i >= bin.length) { return null; } if (bin[i] == false) { bin[i] = true; return bin; } else { bin[i] = false; i++; return binAddBit(bin, i); } } function iniq(arr) { let result = []; let object = {}; arr.forEach(vector => { value = vector.sort(function(a, b) { return a - b }); key = value.join(','); object[key] = value; }); for (var key in object) { result.push(object[key]); } return result; } // Нахождение комбинаций // Ограничение: // На вход только положительные без нулей // На вход массив осортированный по возрастанию // в качестве суммы только положительное значение function _combine(arr, sum = 10) { let result = []; // Частный случай if (arr[0] > sum) return []; if (arr[0] == sum) return [ [sum] ]; //1. Ограничиваем вектор let $aKey = {}; let $a = []; let $sum = 0; // Нулевой элемент массива $aKey[arr[0]] = arr[0]; $a.push(arr[0]); $sum += arr[0]; let $eqSum = false; for (let i = 1; i < arr.length; i++) { if ((arr[i] + arr[0]) <= sum) { //-----------------------------// // count*element < sum $aKey[arr[i]] = $aKey[arr[i]] != undefined ? $aKey[arr[i]] += arr[i] : arr[i]; if ($aKey[arr[i]] < sum) { $a.push(arr[i]); $sum += arr[i]; } //-----------------------------// //-----------------------------// // count*element = sum if ($aKey[arr[i]] === sum) { let $res = []; for (let j = 0; j < (sum / arr[i]); j++) { $res.push(arr[i]); } result.push($res); } //-----------------------------// } if (arr[i] == sum) { $eqSum = true; } } if ($eqSum) { result.push([sum]); } if ($sum < sum) return result; if ($sum == sum) { result.push($a); return result; } // Бинарный инкримент let bin = createBin($a.length); while (change = binAddBit(bin)) { let $sum = 0; let $comb = []; for (let i = 0; i < change.length; i++) { if (change[i] == false) continue; $sum += $a[i]; if ($sum > sum) break; // exit in accumulate $comb.push($a[i]); if ($sum == sum) { result.push($comb); } } } return result; } //------------- helpers --------------------// //--------------------------------------------// let result = []; // Сначала разбиваем массив на положительные и отрицательные значения // Потом сортируем - так быстрее let zero = false; // Существует ли в массиве нулевые значения let posetive = []; let negative = []; let sumPosetive = 0; arr.forEach(element => { if (element === 0) { zero = true; } if (element < 0) { negative.push(element); } if (element > 0) { posetive.push(element); sumPosetive += element; } }); // Сортируем векторы (по модулю) posetive.sort(function(a, b) { return a - b }); negative.sort(function(a, b) { return b - a }); // Если сумма всех положительных элементов меньше эталона, то // Вектор не имеет значений удовлетворяющих условию if (sumPosetive < etalon) return []; // Частный случай равенства всех положительных значений if (sumPosetive == etalon) { result.push(posetive); if (zero) { let _clone = posetive.slice(); _clone.push(0); result.push(_clone); } return result; } // Поиск в векторе из положительных элементов; result = result.concat(_combine(posetive, etalon)); // SUPPLE - Ограничение вектора с положительными числами реализован в методе перебора combinPosetiveLim negative = negative.filter(function(value) { return -value <= (sumPosetive + etalon); }); // Находим все сочетания (использую биннарный инкремент) let bin = createBin(negative.length); // Булевый вектор while (changeBin = binAddBit(bin)) { let sum = etalon; let vector = []; // Сохраняем вектор из отрициталеьных чисел for (let i = 0; i < changeBin.length; i++) { if (changeBin[i] == false) continue; sum -= negative[i]; vector.push(negative[i]); } if (sum > (sumPosetive + etalon)) continue; let lines = _combine(posetive, sum); lines.forEach(value => { result.push(vector.concat(value)); }); } // добавляем элементы с 0 if (zero) { result.forEach(item => { let _clone = item.slice(); _clone.push(0); result.push(_clone); }); } result = iniq(result); return result; }
ссылка на оригинал статьи https://habr.com/ru/post/460923/
Добавить комментарий