Задача
Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых равна 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;
}
Комментарии (82)
usharik
22.07.2019 15:55Задумался, прокатит ли тут динамическое программирование…
neurocore
22.07.2019 16:52Прокатит. Имеем подзадачи A и B со множествами решений соответственно X и Y, тогда решение задачи A+B будет X*Y (декартово)
usharik
22.07.2019 17:25Создаем массив count[10].
- Индекс массива — сумма для которой ищем количество комбинаций. В нулевом элементе будет 1, т.к. ноль можно получить только одним способом, а именно из нуля элементов исходного массива.
- Для единичной суммы — считаем количество элементов равных 1 и записываем в count[1]
- Для суммы равной двум каждый элемент равный двум даст одну последовательность (count[0]), а равный одному — уже посчитанную в count[1].
- Для суммы равной k, i-й элемент массива даст count[k-arr[i]], если он меньше или равен k. Далее все сведется к двум вложенным циклам и сложности O(10*N)~O(N).
- Пункт 2 тоже сводится к пункту 4. Количество единиц отдельно считать не надо.
Но это только подсчет количества, только для положительных чисел и без вытаскивания самих последовательностей.
Ketovdk
23.07.2019 12:35я долго залипал и вроде как не нашел решения лучше, чем meet in the middle с асимптотикой 2^(n/2). Идея:
Входной массив разделить на две части. Для левой части посчитать всевозможные комбинации и забить в хэш-таблицу с ключем, равным сумме элементов в комбинации и значением, равным списку этих комбинаций с такой суммой(ну или количеству, если нужно только количество).
Далее перебираем всевозможные комбинации справа и ищем для них в этой таблице подходящее по сумме значение (10- текущая сумма).
Вроде как до n=40 отрабатывает мгновенно.
Есть ощущение, что полиномиального решения нет. Если у кого-то есть идеи с полиномиальной сложностью-пишитеpan-alexey Автор
23.07.2019 14:32По вашей логике имеем массив из N элементов, мы разбиваем на N/2. После чего перебираем комбинации для N/2 = 2^(N/2), но у нас 2 массива, поэтому общее количество будет 2^(N/2) * 2^(N/2) = 2^N. Я понял к чему вы имели ввиду, это работает если мы используем многопоточные вычисления
Ketovdk
23.07.2019 14:44вы не правы, на самом деле, мы одну половину считаем полностью, а когда считаем вторую половину, то мы уже знаем, какое именно значение из первой половины нужно (10-текущее значение), а оно уже подсчитано и хранится в хэш-таблице
pan-alexey Автор
23.07.2019 14:52Я не хотел бы спорить с вами, возможно вы и правы. Наиболее удачным будет, если вы попробуете реализовать свою идею, буду очень признателен.
Ketovdk
24.07.2019 10:35вариант, который считает количество ответов#include <iostream> #include <vector> #include<map> #define var auto #define ll long long #define ull unsigned long long #define end '\n' using namespace std; int vSize; vector<ll> values; bool increase(vector<bool>& input) { for (int i = vSize - 1; i >= 0; --i) { if (input[i]) { input[i] = false; } else { input[i] = true; return true; } } return false; } ll calcValue(vector<bool>& input) { ll s = 0; for (int i = 0; i < vSize; ++i) { if (input[i]) s += values[i]; } return s; } int main() { ll n; cin >> n; map<ll, ll> answerCnt; vSize = n / 2; for (int i = 0; i < vSize; ++i) { ll x; cin >> x; values.push_back(x); } var flags = vector<bool>(vSize, false); answerCnt[calcValue(flags)]++; while (increase(flags)) { answerCnt[calcValue(flags)]++; } vSize = n - vSize; values.clear(); for (int i = 0; i < vSize; ++i) { ll x; cin >> x; values.push_back(x); } flags = vector<bool>(vSize, false); ll totalCnt = 0; totalCnt += answerCnt[10 - calcValue(flags)]; while (increase(flags)) { totalCnt += answerCnt[10 - calcValue(flags)]; } cout << totalCnt; }
m1ld
22.07.2019 15:55+5Я думаю это вам надо было отправить hr-менеджеру, который вас приглашал на интервью. А не искать сотрудников яндекса тут.
Static_electro
22.07.2019 15:56-1С первого взгляда, задача простая, всего то надо написать рекурсию и перебрать все значения...
Со второго взгляда задача решается за O(n). Автор, я потерял нить рассуждений после шага 1.
MarazmDed
22.07.2019 16:05Со второго взгляда задача решается за O(n). Автор, я потерял нить рассуждений после шага 1.
Классическая задача о загрузке рюкзакаStatic_electro
22.07.2019 16:08Нет же. При чем тут рюкзак? Там надо набрать как можно больше "вещей", общим "весом" не больше заданного. Здесь — строго пары чисел с точной суммой.
Upd: сходил на вики, проверить себя, что не путаю задачу о ранце ни с чем другим. Нет, не путаю, NP-полная. Здесь все гораздо проще.
mayorovp
22.07.2019 16:50+1А где в задаче сказано про "пары"? Я вижу только упоминание "комбинаций".
Static_electro
23.07.2019 07:28+1Точно, ваша правда. А я — невнимательный дурень, увидел знакомые слова и кинулся комментировать, обычно на тестах спрашивают старую добрую задачку про пары. Неужели в Яндексе тестовое с np-полной задачкой?
MarazmDed
22.07.2019 18:25Нет же. При чем тут рюкзак? Там надо набрать как можно больше «вещей», общим «весом» не больше заданного. Здесь — строго пары чисел с точной суммой.
Берете алгоритм для рюкзачной задачи и модифицируете под себя. Емкость рюкзака = 10. Все что меньше — отбрасываете.
pan-alexey Автор
22.07.2019 16:18+1Да, действительно, задача о рюкзаке, должна стремиться, а тут необходимо все варианты. Две разные задачи
Ayahuaska
22.07.2019 18:37+1Со второго взгляда задача решается за O(n).
Как?mayorovp
22.07.2019 20:36Динамическим программированием. Это же просто вариация задачи о рюкзаке.
Ну, если точнее, это будет не совсем O(n), а O(n + k), где k — размер ответа.
imanushin
22.07.2019 23:35А можно чуть больше деталей? Я нашёл задачу о рюкзаке, однако она формулируется по-другому, плюс является NP полной. И не поддерживает отрицательных чисел.
Условно, если числа выглядят как ниже, то только вывод ответа займет O(N*N): 10 -10 10 -10 10 -10… 10
Ketovdk
23.07.2019 09:42для решения задачи о рюкзаке динамикой необходимо отсутствие отрицательных чисел, а также сумму не строго равную 10-ти, как в этой задаче, а НЕ ПРЕВОСХОДЯЩУЮ 10. И рюкзачная динамика ищет самый большой случай, а не все варианты.
Кстати, предположение автора использовать в решении общего случая (с отрицательными числами) решение только для положительных в корне не верно, т.к. вы в решении для положительных отмели большое количество чисел, которые могут использоваться в случае с отрицательными. Например: -15 5 5 15. Вы уберете число 15 и потеряете один случай.mayorovp
23.07.2019 11:44Найти все варианты как раз не проблема: динамикой определяется прежде всего возможность набрать нужную сумму нужным подмножеством — а дальше можно применять обычную рекурсию для перебора вариантов, но уже с ранним отсечением невозможных ветвей. Отсюда и O(n + k).
А вот отрицательные числа и правда всё портят.
Ketovdk
23.07.2019 12:02как раз таки проблема, потому-что нужно хранить сразу ВСЕ решения для каждого размера, а не только лучшее
mayorovp
23.07.2019 12:04Не "все решения для каждого размера", а "признак возможности для каждого размера и префикса".
Ketovdk
23.07.2019 12:06так нет, вам же нужно будет потом их вывести еще, так-что нельзя их терять (ну если надо просто посчитать, то все-равно не признак, а количество).
mayorovp
23.07.2019 12:15-1Я же писал, выводить их потом рекурсивным поиском за O(k).
vitaliy2
24.07.2019 20:05Решить задачу за O(n+k) невозможно. Например, используя всего лишь массив из 93668 чисел от 1 до 10000 (10к единиц, 5к двоек, 3333 троек и т.?д.) можно получить 3.6*10106 комбинаций, набирая всего лишь сумму 10000. Один только их вывод займёт бесконечность.
mayorovp
24.07.2019 20:54Один только их вывод займёт бесконечность.
Так ведь именно этот фактор я и учёл под буквой k...
vitaliy2
24.07.2019 21:01Я думал k — сокращённый диапазон чисел (который равен искомой сумме при отсутствии отрицательных чисел). Так то итак понятно, что за O(кол-во комбинаций) можно вывести без проблем.
Сама по себе задача неинтересная, но очень интересная задача — оценить асимптотику количества комбинаций. Понятное дело, что она не выше O(2?) (т.?к. даже если брать все суммы, то в худшем случае этих сумм никогда не будет больше 2?), но чему конкретно она равна в самом худшем случае, когда мы берём только одну сумму? Вот это интересная задача, но мне лень думать)vitaliy2
25.07.2019 00:01Асимптотика точно не лучше O(2?/n?), т.?к. существует алгоритм выбора элементов, чтобы вышло не менее 2?/(n?+n)*2 вариантов для определённой суммы.
Алгоритм такой: просто берём все числа по порядку от 1 до n. Поскольку повторений среди чисел нет, общее количество их комбинаций — ровно 2?. При этом максимальная их сумма не может превышать (n?+n)/2 (по формуле арифметической прогрессии), а минимальная сумма — 1. Соответственно, суммарное количество возможных сумм равно ровно (n?+n)/2 (от 1 до (n?+n)/2).
В итоге имеем 2? комбинаций чисел и (n?+n)/2 разных сумм. Это значит, что даже если бы все эти суммы встречались равномерно, на каждую должно приходиться 2?/(n?+n)*2 комбинаций чисел. В реальности комбинаций на лучшую из сумм будет приходиться ещё больше, т.?к. суммы встречаются неравномерно, но несмотря на это мы всё-равно смогли неслабо увеличить минимальную оценку комбинаций одной суммы в одном из худших случаев.
В итоге в худшем случае может попасться как минимум 2?/(n?+n)*2 вариантов суммы либо ещё больше, а насколько больше, я пока не знаю. Но это число точно не превышает 2?, т.?к. даже комбинаций всех сумм не может быть больше, чем 2?. Как итог из-за длинного ответа асимптотика решения не может быть лучше O(2?/n?) (либо является ещё хуже).
PS. Скорее всего приведённый алгоритм и есть оптимальный. Превысить 2? мы всё-равно не можем, поэтому всё, что мы можем делать, это улучшать делитель, который равняется (n?+n)/2 или меньше. Но как только мы начнём улучшать его, нам придётся жертвовать 2?, т.?к. это значит, что мы начнём повторять числа, а повторения вместо того, чтобы увеличивать количество комбинаций экспоненциально (2?) увеличивают их линейно. В итоге ради уменьшения n? (которое есть в 2?/(n?+n)*2) мы жертвуем 2?. Глупо. Но это пока не доказательство, просто интуиция. Но если моя интуиция верна, то нормальное решение (которое несложное, но требует O(n*k) памяти, где k — размеры чисел) будет работать за O(2?/n?) или насколько-то дольше (т.?к. я не считал разброс неравномерности сумм).Ketovdk
25.07.2019 10:57я уже привел алогритм за 2^(n/2) для подсчета количества комбинаций и 2^(n/2) + k, где k-количество ответов для вывода всех вариантов (ну и если элементы могут повторяться, то k в худшем случае 2^(n-1), например когда одна десятка и все нули)
Хотя по оценке есть вопросы:
(n?+n)/2 (по формуле арифметической прогрессии), а минимальная сумма — 1. Соответственно, суммарное количество возможных сумм равно ровно (n?+n)/2 (от 1 до (n?+n)/2).
не понятно, причем тут формула арифметической прогрессии, они не обязательно последовательны. И почему минимальная сумма — 1, если могут быть отрциательные.vitaliy2
25.07.2019 13:12не понятно, причем тут формула арифметической прогрессии, они не обязательно последовательны. И почему минимальная сумма — 1, если могут быть отрциательные.
Они последовательны именно в моём алгоритме. Отрицательных тоже в моём нет.
Если бы они были непоследовательны, то общее количество сумм увеличилось бы, и на каждую сумму стало бы приходится меньше вариантов, а нам же нужно наоборот дать верхнюю оценку вариантов.Ketovdk
25.07.2019 13:39ну это не совсем правда, т.к. если они непоследовательны (например одинаковы), то 2^(n-1), пример я привел, следовательно верхняя граница не верна
vitaliy2
25.07.2019 13:43Если они одинаковы, то, наоборот, количество комбинаций резко падает.
Если взять все числа от 1 до 30, у нас есть 1073741824 (2?) их комбинации. Но если все эти числа будут одинаковыми, например, единичками (или любым другим числом), получим всего лишь 31 вариант (n+1).
Возможно, в каких-то случаях выгодно взять немного одинаковых чисел в каком-то диапазоне, по крайней мере у меня нет доказательства, что это неправда, но скорее всего, думаю, это неправда. Даже одно одинаковое число среди всех чисел уменьшит суммарное количество комбинаций уже в 1.33 раза. Если мы сможем на какой-то сумме увеличить более чем в 1.33 раза, то это будет выгодно. Но я не уверен, что сможем вообще (т.?к. та сумма, которая по центру, т.?е. равна (n?+n)/4 итак имеет высокую вероятность встречи).
Я чуть позже прикину кол-во комбинаций на лучшей сумме, из-за неравномерности сумм оно, вероятно, O(2?/n) или что-то типа того (т.?к. чем дальше отклоняемся от центральной суммы, тем ниже вероятность на неё попасть).Ketovdk
25.07.2019 13:51так я же привел пример, когда n-1 ноль и одна десятка. Тогда понятно, что ответов 2^(n-1)
vitaliy2
25.07.2019 13:54Это почему ещё? Если одна десятка и остальные нули, а ищем десятку, то будет всего лишь n комбинаций, что очень мало.
Первая комбинация 10.
Вторая 10 0
Третья 10 0 0
…
Последняя 10 0 0 0 … 0 0 0
Суммарно ровно n комбинаций.Ketovdk
25.07.2019 14:00но это не все комбинации, обычно подразумевается с учетом порядка (ну точнее не с учетом порядка, а с учетом места, то есть один ноль отличается от другого, если стоит на другом месте). Хотя конечно смотря как считать
vitaliy2
25.07.2019 14:06Цитирую:
Напишите функцию, которая из произвольного входящего массива выберет все комбинации чисел, сумма которых равна 10
Комбинации чисел, а не их позиций. Т.?е. если есть два нуля — это одинаковые числа, и количество комбинаций при их перестановке не увеличится, т.?к. нам нужна именно комбинации чисел, а не их индексов.
0 и 0 — это абсолютная такая же комбинация, что и 0 и 0 (я кэп), даже несмотря на то, что эти нули были взяты с разных мест.
Вообще для отсутствия разночтения в задачах обычно приводят примеры ответа + подробнее описывают условие. Здесь конечно вина автора. А если не было описано, лучше уточнить на всякий случай.
imanushin
23.07.2019 12:21Найти все варианты как раз не проблема
А можно всё-таки вас попросить накидать псевдокод? По моим не самым эффективным алгоритмам, просто вывод результата требует
O(n*k)сложности. Например, если у вас идут возрастающие числа (ну т.е. 1, 2, 3… n) и надо вывести все комбинации для2*n.Ayahuaska
23.07.2019 13:49Там разве не придётся проверить все комбинации?
ЗЫ.
Я туплю или в массиве из N-элементов, количество комбинаций будет 2^n-1?
pan-alexey Автор
23.07.2019 15:31-15 не потеряется. В этом и смысл отдельно рассматривать только положительные. Для вашего вектора он попадает в шаг 3. т.е. искомый вектор [-15,5,5,15] => [5,5,15] но значение будет уже не 10 а 25. Т.е, в данном случае и получиться единственное сочетание дает нам сумма 25 = [5,5,15], как результат:
Только для положительных => [5,5]
Для отрицательных => [-15*,5,5,15]
Ответ [ [ 5, 5 ], [ -15, 5, 5, 15 ] ]
ferosod
22.07.2019 15:56-1for (item in list) {
if (list.contains(10-item)) {
print(item, 10-item)
}
}
fireSparrow
22.07.2019 16:04+1Во-первых, это квадратичная сложность.
Во-вторых, оно не работает для комбинаций из более чем двух чисел.
koropovskiy
22.07.2019 16:10То есть обрезаем под вектора до того момента, чтобы их сумма была меньше 10, а те что равны 10 добавляем в результат:
и
[2, 2, 2, 2, 2] => [2, 2, 2]
Ок. В результат добавили 2+2+2+2+2, но куда делась четвертая двойка из «вектора»?
результат 2+2+2+2+1+1 потерян :(pan-alexey Автор
22.07.2019 16:15да, все верно, ровно до 10, реализовал именно с равенством + Суть моих размышлений такая, что не имеет смысл рассматривать комбинации из повторяющихся чисел, если их количество*значение > 10.
спасибо за ошибку, исправил
FenixFly
22.07.2019 16:12Для того, чтобы обработать отрицательные числа, нужно найти наименьшее число в векторе, и сместить все числа в векторе и требуемую сумму на модуль этого числа, считаю что это более правильный подход, поскольку мы не меняем алгоритм.
fireSparrow
22.07.2019 16:24Если каждое слагаемое смещаем на A, то требуемую сумму нужно сместить на (n*A), и n будет отличаться от случая к случаю. И это уже никак не впихнуть в тот же самый алгоритм.
Fyret
22.07.2019 16:41Уверен, ответом на подобные задачи является алгоритм, оформленный хотя бы в виде псевдокода, и оценка его сложности. Здесь ничего этого нет. А задачка заставляет подумать, это да.
truebest
22.07.2019 16:59Я, если решал такую задачу, выполнил бы сортировку и отбросил все лишнее большее либо равное 10. А дальше сделал бы алгоритм игры Очко, набирая число для нужного значения, при этом пропуская шаги где предыдущий стартовый элемент, равен следующему. Также можно подумать как зеркальные результаты отбросить(типа 1 + 9 или 9 + 1).
Актуальные алгоритмы, как из АУЕ сделать программиста!
dss_kalika
22.07.2019 17:03+1Отрицательные числа не позволят ограничить диапазон.
Вопрос ещё с неуникальными элементами )truebest
22.07.2019 17:15Отрицательные числа не позволят ограничить диапазон.
Ну а куда деваться если про них не сказано в задании. С другой стороны, можно также проверить сложить все положительные и отрицательные числа в две переменные. Точкой равновесия выбрать 10, при сильном перевесе в отрицательную сторону отбрасывать числа, но тогда и на вход нужно подавать все числа в том числе и больше 10. Все же очко это для положительных чисел.dss_kalika
22.07.2019 17:38ну так и про строгоположительные не говорилось )
Да и равновесие, конечно, хороший метод, но что то, мне кажется, он не будет сильно лучше сурового перебора )truebest
22.07.2019 17:51Надо оформить еще одну статью на хабр от себя и написать свое обдуманное и эффектное решение этой задачи, потом уже обсуждать.
А по факту это мат задача, тут не программистом а математиком-алгоритмистом надо быть. Это как 2 в 64 возводить в лоб, для этого уже есть алгоритмы, которые просто нужно знать.
Я скорее хотел сказать, какой подход я бы применил решая эту задачу.MarazmDed
22.07.2019 20:10А по факту это мат задача, тут не программистом а математиком-алгоритмистом надо быть.
Воу-воу. А программист не должен быть математиком-алгоритмистом? Точно-точно?truebest
22.07.2019 20:27Вообще нет. Многие из нас читали книги, типа Рода Стивенса «Алгоритмы», наверное многие знают основные алгоритмы и структуры данные, знают про асимптотическую сложность и тд. НО!
Задачи разными бывают, например мои коллеги и я программисты, в том числе ПЛИСовики, писали код, на основе алгоритмов, разработанных алгоритмистами и математиками. Потому-что банально не каждый программист знает хорошо цифровую обработку сигналов, не знает как входящий поток байт, обработать и преобразовать требуемый выходной массив. Но в сфере компетенций его находится конечная реализация, на c/c++ или asm она будет решает программист иногда советуясь с алгоритмистом.MarazmDed
23.07.2019 13:19Честно говоря, вопрос был риторическим :) Программист (а не кодер) должен быть и математиком и алгоритмистом. Дискретка, теория графов, теория вероятностей, мат. статистика, линейная алгебра да и матан, чего уж греха таить — это must have для программиста.
Другое дело, что правило Парето действует везде: 80% задач — не требуют знаний вообще, 20% задач — требуют глубоких знаний. Но все же, программистом принято считать не аникейщика, а человека, хотя бы краем глаза знакомого с математикой.
oam2oam
22.07.2019 17:08+1Понятно, что для N входных чисел существует 2^N сумм этих чисел. Вопрос стало быть, можем ли мы каким-то способом уменьшить этот перебор? Если нет, то ответ к задаче — O(2^N).
pan-alexey Автор
22.07.2019 17:16Я не пишу что при любых значениях N — скорость будет равнятся какой либо зависимости. в качетве теста на выборке имеется профит в 42%. Это утверждение говорит что количество итераций может варьироваться от 0 до 2^N + C
ihost
22.07.2019 17:08Это задача о сумме подмножеств и имеет псевдополиномиальное время решения в общем случае.
Новенькие интересные алгоритмы можно посмотреть здесь или погуглить более широко.
В любом случае непонятно, почему минусят автора статьи, и тем более откуда предлагаются решения с линейной или квадратичной сложностью: пока не доказано P=NP — это невозможно решить быстрее.
GCU
22.07.2019 17:30Предположу что автора минусят за отвратительный текст.
«Тестовачая» «состоит из числе»
Стоило бы проявить капельку уважения к читателям — убрать воду и исправить явные ошибки.
Если это такой юмор, то он непонятен.
oam2oam
22.07.2019 17:16Простой пример. Пусть входная последовательность длины N состоит из числа 10 и остальных нулей. Тогда для задачи из статьи есть ровно 2^(N-1) решений — это число 10 и все варианты остальных элементов.
usharik
22.07.2019 17:32Маленькое обращение к автору. Вы научились пользоваться сортировкой для построения эффективных алгоритмов. Увы, далеко не все задачи решаются с её помощью. Пришло время разобраться с динамическим программированием! Задачи на его применение суперчасто встречаются на собеседованиях из-за их неочевидности для неподготовленного кандидата.
pan-alexey Автор
22.07.2019 17:52Большое спасибо, но с чего вы взяли что я не разобрался с динамическим программированием? Потому что я не использовал рекурсию? Рекурсивные функции оправданны, но в конкретном примере я обошелся без них, но никто не говорит что их нельзя использовать для данной задачки. Если будет время попробую реализовать путем разбиения на множество под векторов с использованием динамического программирования.
usharik
22.07.2019 17:59Возможно я высказался слишком категорично, но то как вы пытаетесь использовать сортировку меня навело на такие мысли. Не в коем разе не хотел вас обидеть и буду рад, если ошибся.
Из моего личного опыта, сортировка нужна там, где речь идет о поиске, а динамическое программирование, когда задача поиска комбинаций или оптимизации.
iroln
23.07.2019 01:11Задачи на его применение суперчасто встречаются на собеседованиях из-за их неочевидности для неподготовленного кандидата
Подготовленного в чём? Уметь решать на собеседовании абстрактные задачи методом динамического программирования? Человека берут на работу для участия в олимпиадах по программированию? :)
Как часто вам в работе приходится решать практические задачи с динамическим программированием, когда нужно было реализовывать именно какой-то алгоритм или часть алгоритма?
Мне вот один раз всего приходилось для "minimum cost path". В прототипе. Потом всё равно выбросили и взяли production ready библиотеку с алгоритмами на графах.
Тут просто как раз статья параллельно :)
https://habr.com/ru/post/460901
cross_join
22.07.2019 18:15С отрицательными числами получается другая задачка, так как длинная комбинация может включать в себя более короткую. Либо нужно вводить ограничение на поиск минимальных комбинаций, а это тоже меняет дело.
P.S. Выше заметили, что и при наличии нулей возникает неопределенность.
GCU
22.07.2019 18:49А в чём смысл сначала сортировать элементы, а потом удалять?
На мой взгляд эффективнее сначала удалять, а уже потом сортировать остаток.
Spaceoddity
23.07.2019 02:12Про массив вообще ничего не сказано. С чего ТС решил что там будут только НАТУРАЛЬНЫЕ ЧИСЛА?
pan-alexey Автор
23.07.2019 14:28Эм, а с чего вы взяли что это не будет работать и дробными числами?
Spaceoddity
23.07.2019 14:39-1Эм, ну с отрицательными точно не будет работать. Я уж молчу про всякие комплексные числа.
Да у вас там даже приведения типов нет — а если в массиве будут строки?
Ну и как это будет работать с [29/3, 1/3]?
Ketovdk
23.07.2019 12:03есть точное решение за 2^(n/2)+количество ответов через MIM. Ну или просто 2^(n/2) если нужно посчитать количество вариантов, а не выводить их. Есть ощущение, что оно оптимальное. Если заинтересует, могу попробовать описать.
wibotwi
Очень тяжело читать, поправьте пожалуйста опечатки в тексте. Во многиз браузерах есть встроенный спеллчекер.