Внезапно возникла такая задача:
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мс вряд ли получится соптимизировать код
Здравствуйте, xma, Вы писали:
xma>натуральных или неотрицательных целых ?
неотрицательных.
xma>a*2 = 3, (для проверки числа 3)
Для пары чисел это сводится просто к кратности xma>a*2 + b*3 = 5, (для проверки числа 5)
Ага. xma>a*2 + b*3 + c*5 = 10, (для проверки числа 10)
Ага.
xma>ну и числа которые являются линейной комбинацией других — можно наверное сразу удалять и не добавлять в новое уравнение (для последующих чисел)
Да, конечно.
S>>Натуральные. xma>а сами числа (не коэффициенты) — натуральные и большие единицы, я так понимаю ?
Да, если минимальный равен единице то решение тривиально.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, gandjustas, Вы писали:
G>a=0, b=1, c=3, d=0 G>Несложно перебирается даже в уме. Почему компьютеру не доверить эту задачу?
можно конечно доверить, если скорость неважна — но твоё решение почти на два (а то и почти три) порядка медленнее чем требуется автору .. (подробнее, тут
ну т.е. я так понял что затруднений с решением линейных диофантовых уравнений с произвольным числом неизвестных — теперь у тебя нету (в целых числах), но ты пока ищешь подход к решению их в неотрицательных целых ? (для коэффициентов)
Здравствуйте, xma, Вы писали:
xma>Здравствуйте, Sinclair, Вы писали:
S>>Ага.
xma>ну т.е. я так понял что затруднений с решением линейных диофантовых уравнений с произвольным числом неизвестных — теперь у тебя нету (в целых числах), но ты пока ищешь подход к решению их в неотрицательных целых ? (для коэффициентов)
xma>
Ага. Впрочем, есть подозрение, что это лютый оверкилл, т.к. перебор вполне себе работает даже и без мемоизации.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, xma, Вы писали:
xma>Здравствуйте, gandjustas, Вы писали:
G>>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI G>>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14 xma>батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф
)
Нет там никаких сотен. https://dotnetfiddle.net/EJ8xem
Чтобы добраться до 1мс, пришлось увеличить и максимум и количество чисел в 10 раз. И это — без мемоизации.
xma>до миллисекунды вряд ли "тупым перебором" можно до оптимизировать
уже
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, xma, Вы писали:
xma>>Здравствуйте, gandjustas, Вы писали:
G>>>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI G>>>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14 xma>>батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф
) S>Нет там никаких сотен. https://dotnetfiddle.net/EJ8xem S>Чтобы добраться до 1мс, пришлось увеличить и максимум и количество чисел в 10 раз. И это — без мемоизации.
Не то измерено, filtered лениво вычисляется
xma>>до миллисекунды вряд ли "тупым перебором" можно до оптимизировать S>уже
Я пооптимизировал децл, 20 мс получилось https://dotnetfiddle.net/q51ICI
Мемоизация не особо помогла.
Здравствуйте, Sinclair, Вы писали:
S>Внезапно возникла такая задача: S>1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17 S>2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.
S>Эта задача похожа на задачу о сдаче
: если отсортировать исходную последовательность во возрастанию, то она сводится к вопросу "можно ли разменять число набором монет с номиналами, представленными левее в списке"? То есть нас не интересует ни само количество вариантов, ни поиск варианта с минимальным количеством монеток. S>Просто нужно знать — есть ли такой вариант или нет.
S>Есть идеи, куда копать?
Похоже на основную задачу линейного программирования, но не она.
Поэтому следующая идея, может пригодится. Предупреждаю, что не проверял, "as is", no warranty.
Идея в том, что можно легко повыкидывать огромное кол-во элементов, которые представимы линейной комбинацией двух элементов.
Т.е. решение не исчерпывающее, но вроде как может быть практичным.
Обозначим исходное множество, сразу будем считать его упорядоченным по возрастанию, как М.
Обозначим результирующее мн-во как B (база).
Если для числа x выполняется пункт 2. относительно B, то будем говорить что x представимо (с натуральными весами) в B.
Алгоритм: вначале B пустое. Множество М содержит m элементов.
* Берем первый (наименьший) эл-т e0 из M и переносим его в B.
* Теперь перетащим из M в B все минимальные элементы x с различными значениями (x mod e0). Для этого проходим по M и
если для элемента i выполнено (i mod e0)=0 или (i mod e0)=(b mod e0) для некоторого эл-та b из B, то просто выбрасываем i из M,
иначе переносим i в B.
Очевидно, что по дороге если мы накопили e0 элементов в B, то дальше можно просто занулить M, т.к. все остальное не добавит
ничего в B.
* По окончании предыдущего шага М пустое и B является базой для исходного полного M, при этом любой элемент из M представим
максимум двумя элементами (с натуральными весами) из B.
Сложность по времени O(m). Чем ближе e0 к 1, тем лучше.
(важно с точки зрения того, насколько возможен перебор в лоб, или надо пытаться как то оптимизировать)
на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ? (ну и как бэ разница есть, 3000G это или 7950X, 3050 или 4090)
