Внезапно возникла такая задача:
1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17
2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.
: если отсортировать исходную последовательность во возрастанию, то она сводится к вопросу "можно ли разменять число набором монет с номиналами, представленными левее в списке"? То есть нас не интересует ни само количество вариантов, ни поиск варианта с минимальным количеством монеток.
Просто нужно знать — есть ли такой вариант или нет.
Есть идеи, куда копать?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
так исходный массив возрастающих (и не повторяющихся) чисел, или нет ? (если в одномерном виде)
S>Есть идеи, куда копать?
не понятно — насколько большой массив и насколько большие числа в нём могут быть ? (важно с точки зрения того, насколько возможен перебор в лоб, или надо пытаться как то оптимизировать)
также не понятно за какое время должна выполняться программа ?
так что вынужден констатировать что твоё ТЗ как выступающего в роли системного "аналитега" — говно
Здравствуйте, xma, Вы писали: xma>так исходный массив возрастающих (и не повторяющихся) чисел, или нет ? (если в одномерном виде)
Исходный — нет, но за nlogn его можно сделать возрастающим.
xma>не понятно — насколько большой массив и насколько большие числа в нём могут быть?
Произвольно, заранее неизвестно. xma> (важно с точки зрения того, насколько возможен перебор в лоб, или надо пытаться как то оптимизировать)
Перебор в лоб считаем невозможным. Там комбинаторный взрыв наступает очень быстро. xma>также не понятно за какое время должна выполняться программа ?
В пределах миллисекунды — это часть гораздо более объёмной задачи, которая должна успевать выполняться за десятки миллисекунд, при этом конкретно эту задачу надо будет решать многократно. xma>так что вынужден констатировать что твоё ТЗ как выступающего в роли системного "аналитега" — говно
Ну, что было — то представил. Покажите пример вашего ТЗ для алгоритма, чтобы у меня был образец для подражания.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Исходный — нет, но за nlogn его можно сделать возрастающим.
шо за пургу ты несёшь ? как ты одномерный массив состоящий из пар (10, 2), (1, 5) сделаешь одномерно возрастающим ? (так чтобы пары сохранились в последовательности)
S>Произвольно, заранее неизвестно.
натуральные или целые ? обычные int 4 байта ?
S>В пределах миллисекунды
взаимоисключающие требования на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ? (ну и как бэ разница есть, 3000G это или 7950X, 3050 или 4090)
ну и приблизительно сколько чисел — тысячи / миллионы или миллиарды ? (в последнем случае на миллисекунду думаю что рассчитывать маловероятно)
S>Ну, что было — то представил. Покажите пример вашего ТЗ для алгоритма, чтобы у меня был образец для подражания.
можно предположить что (если задача имеет быстрое решение, то) тут фишка где то в диофантовых уравнениях — и если нужно очень быстро и точно, то копать куда то туда (я их лично не проходил, в школьной программе их тогда вроде отменили)
Здравствуйте, xma, Вы писали: xma>шо за пургу ты несёшь ? как ты одномерный массив состоящий из пар (10, 2), (1, 5) сделаешь одномерно возрастающим ? (так чтобы пары сохранились в последовательности)
Тут нет никаких пар. Есть множество чисел. Попарно различных — это означает, что каждое число встречается в нём не более 1 раза.
xma>натуральные или целые ? обычные int 4 байта ?
Натуральные.
S>>В пределах миллисекунды xma>взаимоисключающие требования на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ?
На обычном CPU, предпочтительно в однопотоке. Задача — гражданская, мы не будем выдвигать никаких требований к аппаратуре. xma>ну и приблизительно сколько чисел — тысячи / миллионы или миллиарды ? (в последнем случае на миллисекунду думаю что рассчитывать маловероятно)
Пусть будут десятки чисел. xma>можно предположить что (если задача имеет быстрое решение, то) тут фишка где то в диофантовых уравнениях — и если нужно очень быстро и точно, то копать куда то туда (я их лично не проходил, в школьной программе их тогда вроде отменили)
Да явно имеет. Интуитивно кажется, что для взаимно простых n и m любое число больше (n-1)*(m-1) представимо в виде их линейной комбинации; это означает, что "перебирать" придётся относительно небольшое количество чисел.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>На обычном CPU, предпочтительно в однопотоке. Задача — гражданская, мы не будем выдвигать никаких требований к аппаратуре. S>Пусть будут десятки чисел.
Чем перебор не устраивает?
Здравствуйте, Sinclair, Вы писали:
S>Тут нет никаких пар. Есть множество чисел. Попарно различных — это означает, что каждое число встречается в нём не более 1 раза. S>Натуральные. S>На обычном CPU, предпочтительно в однопотоке.
так так так
S>Пусть будут десятки чисел.
а вот это уже другой разговор, батенька
S>линейной комбинации (с целыми коэффициентами)
комбинация я так понимаю — из произвольного числа чисел ? (не только пары)
S>Да явно имеет.
ну тогда, чекай
Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.
конкретно этой статьи достаточно или нет я хз но направление поиска думаю понятно ..
S>Интуитивно кажется, что для взаимно простых n и m любое число больше (n-1)*(m-1) представимо в виде их линейной комбинации; это означает, что "перебирать" придётся относительно небольшое количество чисел.
хз о чём ты, но тебе либо надо нагуглить решение "линейных диофантовых уравнений с любым числом неизвестных" (вроде в статье выше есть набросок, возможно даже полный — детально до конца не вдавался), либо поискать либу (напр., на github) их решающие
S>Внезапно возникла такая задача: S>1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17 S>2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.
S>с целыми коэффициентами
Мойшет-таки с неотрицательными? А то так и 2 представимо как 1*13 + (-1)*11.
S>множество попарно различных
Если множество, то зачем ещё писать что «различных», да ещё и «попарно»?
Здравствуйте, σ, Вы писали:
S>>с целыми коэффициентами σ>Мойшет-таки с неотрицательными?
да, я тоже про это хотел спросить но подумал что если человек говорит с целыми, значит с целыми
σ>А то так и 2 представимо как 1*13 + (-1)*11.
да, косячок в ТЗ — штраф с системного "аналитега"
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, Sinclair, Вы писали:
S>>Есть идеи, куда копать?
S>Динамическое программирование для каждого числа, начиная со второго. Ничего лучше пока не придумывается.
Пока что накопалось следующее:
1. Вопрос — в существовании решения диофантового уравнения вида a1x1+a2x2+a3x3+... = b при натуральных x, a, и b.
2. Вопрос существования решения в целых х сводится к делимости b на GCD(a1,a2,...). То есть если не делится — то b заведомо непредставимо в виде искомой комбинации.
3. Если же b делится на GCD, то его общее решение будет устроено как некоторая линейная комбинация из векторов:
Натуральность xi сводится к существованию решения у системы линейных диофантовых неравенств, xi>=0. На этот раз никаких ограничений на x' уже нет — они могут быть и отрицательными.
Про решения систем неравенств нас учили, но не в целых числах. Надо поднять конспекты и посмотреть, как там оно делалось.
Опять же, есть интуитивная идея, что начиная с какого то B, все b>=B делящиеся на GCD будут представимы. Если получится построить формулу для B — тогда хорошо.
Для b < B можно искать уже динамическим программированием — там объем перебора предсказуем.
Кроме того, мы же решаем не одну задачу, а серию задач, пытаясь добавить в наше множество очередное ai. Мемоизация результатов поиска с предыдущей итерации нам поможет — если любое число d было представимо как комбинация a1...an-1, то и при помощи a1...an оно тоже представимо.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, σ, Вы писали:
σ>Мойшет-таки с неотрицательными? А то так и 2 представимо как 1*13 + (-1)*11.
да, конечно — речь о натуральных коэффициентах.
σ>Если множество, то зачем ещё писать что «различных», да ещё и «попарно»?
Привычка. Часто встречал, что в неформальной постановке путают "множество" и "мультимножество".
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
σ>>Мойшет-таки с неотрицательными? А то так и 2 представимо как 1*13 + (-1)*11. S>да, конечно — речь о натуральных коэффициентах.
натуральных или неотрицательных целых ?
потому что тогда просто можно решать, например для массива (2,3,5,10) (как предварительно отсортированного)
как
a*2 = 3, (для проверки числа 3)
a*2 + b*3 = 5, (для проверки числа 5)
a*2 + b*3 + c*5 = 10, (для проверки числа 10)
где,
a,b,c ∈ Z,
a,b,c >= 0
т.е. просто пробегаясь по всем элементам начиная со второго до последнего
P.S.:
ну и числа которые являются линейной комбинацией других — можно наверное сразу удалять и не добавлять в новое уравнение (для последующих чисел)
S>Натуральные.
а сами числа (не коэффициенты) — натуральные и большие единицы, я так понимаю ?
Здравствуйте, xma, Вы писали:
xma>Здравствуйте, gandjustas, Вы писали:
G>>Чем перебор не устраивает?
xma>решение диофантовых уравнений перебором ?
При чем тут они?
xma>а решение задачи тут
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, gandjustas, Вы писали: S>>>Пусть будут десятки чисел. G>>Чем перебор не устраивает? S>комбинаторикой.
Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI
С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14
Можно пооптимизировать, можно применить ДП, думаю будет еще быстрее
using System;
using System.Linq;
using System.Collections.Generic;
var rnd = new Random();
var numbers = Enumerable.Range(0, 50).Select(_ => rnd.Next(2,1000)).ToArray();
Array.Sort(numbers);
Console.WriteLine($"[{string.Join(", ",numbers)}]");
var filtered = numbers.Where((x, i) => !IsSumOf(x, numbers[0..i]));
Console.WriteLine($"Filtered [{string.Join(", ",filtered)}]");
bool IsSumOf(int x, Span<int> numbers)
{
if (numbers.Length == 0) return false;
var h = numbers[^1];
var mod = x % h;
if (mod == 0) return true;
for (var i = x / h; i>= 0; i--)
{
if (IsSumOf(x - i * h, numbers[..^1])) return true;
}
return false;
}
Здравствуйте, gandjustas, Вы писали:
G>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI G>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14
батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф
а так то мне тоже первое что пришло в голову — перебор (типа если скорость "не важна")
G>Можно пооптимизировать, можно применить ДП, думаю будет еще быстрее
до миллисекунды вряд ли "тупым перебором" можно до оптимизировать
Здравствуйте, xma, Вы писали:
xma>Здравствуйте, gandjustas, Вы писали:
G>>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI G>>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14 xma>батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф
)
Я пропустил про 1мс
G>>Можно пооптимизировать, можно применить ДП, думаю будет еще быстрее xma>до миллисекунды вряд ли "тупым перебором" можно до оптимизировать
До 1мс вряд ли получится соптимизировать код
(важно с точки зрения того, насколько возможен перебор в лоб, или надо пытаться как то оптимизировать)
на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ? (ну и как бэ разница есть, 3000G это или 7950X, 3050 или 4090)
