Комбинатор. Подбор суммы из набора чисел. Обработка для 1С версии 8.х (УФ)

19.05.17

Разработка - Математика и алгоритмы

Как следует из названия, предлагаемая обработка позволит перебрать набор чисел и выбрать те из них, которые в сумме равны заданному числу. Имеется целый ряд настроек, позволяющих проделать эту "титаническую" работу быстро и с комфортом. И если такой набор чисел существует, - он будет найден. А если существует множество таких наборов, - они тоже могут быть найдены (не все, разумеется). Ибо, полный перебор может, в зависимости от мощности набора чисел, потребовать времени, соизмеримого со временем существования Вселенной. А разве мы можем столь долго ждать?

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Комбинатор. Подбор суммы из набора чисел. Обработка для 1С версии 8.х (тонкий клиент):
.epf 21,98Kb
99
99 Скачать (1 SM) Купить за 1 850 руб.

На картинке представлено окно комбинатора:

Что хотелось бы прокомментировать?

Ползунок в обл.1. Его положение указывает, какая часть суммы будет набрана случайным подбором. Чем больше сумма, которую мы пытаемся подобрать, и чем больше чисел в исходном наборе данных, - тем правее располагаем этот ползунок. Не рекомендую использовать 100% случайного подбора, иначе поиск комбинации чисел по времени может сильно затянуться или вовсе не дать положительного результата. Равно как и отказываться от случайного подбора полностью не следует - может статься, что будете ждать результат вечно.

Кнопка открытия в обл.2 устанавливает случайную сумму и запускает подбор. Полезна, если хотите "поиграть" с обработкой.

Время на одну попытку подбора в секундах. Если лимит времени при подборе будет исчерпан, процесс поиска прервется. Нулевое значение не ограничивает во времени процедуру поиска набора чисел путем перебора.

Количество попыток - указывает максимальное количество попыток подобрать требуемую сумму.  Используется, если время на одну попытку ограничено, т.е. больше нуля. Количество попыток со значением -1 не ограничивает это самое количество попыток подбора суммы. Процесс будет длиться до получения нужного результата. Если замечаете, что результата все нет и нет, бесконечную цепь попыток прерываем удержанием клавиши Ctrl. Каждую попытку предваряет новый случайный подбор чисел.

Из моего опыта: время лучше ограничить 15-20 секундами и запустить несколько попыток подбора. Сумму подбирать случайно по максимуму, но не все 100%.

Помеченные суммы в списке слева не учавствуют в случайном подборе.

Помеченные суммы в списке справа все время присутствуют в выборке чисел.

Перемещать суммы между списками можете путем выбора значения в списке (либо нескольких значений сразу).

Что касается исходного набора чисел. Предполагается, что вы его передаете в обработку в списке значений. Но, можно также его получить, нажав кнопку "Заполнить".

В открывшейся форме можете либо сформировать случайный набор чисел, либо получить его из буфера обмена. Из текстового документа, колонки отчета 1С, колонки таблицы Excel... и прочие источники.

Программный вызов осуществляем так:

//Фрагмент кода
//Пример. Все параметры не обязательные
Парам = Новый Структура;

Настройки = Новый Структура;
Настройки.Вставить("ВремяНаПопытку", 6);		//в секундах
Настройки.Вставить("КвоПопыток", 5);
Настройки.Вставить("ПредварительныйПодбор", 75);	//Значение от 0 до 100. Если 0 - не выполняется
							//предварительный (случайный) набор суммы
Настройки.Вставить("Сумма", 795);
Настройки.Вставить("Точность", 0);

Парам.Вставить("Настройки", Настройки);
Парам.Вставить("ВыходПоГотовности", Истина);	//Как только получите результат, - вывалитесь из обработки, если Истина
						//Если Ложь, - придется нажать кнопку "Готово" для завершения
//Лучше, конечно, сначала убедиться в готовности именно ожидаемого результата и нажать кнопку "Готово"

//Здесь должны быть ваши суммы для подбора
СписокДляПодбора = Новый СписокЗначений;
Для Инд = 1 По 300 Цикл
	СписокДляПодбора.Добавить(Инд,Строка(Инд)); 
КонецЦикла;

Парам.Вставить("СписокДляПодбора", СписокДляПодбора);

спРез = ОткрытьФормуМодально("ВнешняяОбработка." + ИмяОбработки + ".Форма", Парам);
//В спРез получили результат

При заполнении набора чисел из буфера обмена, использованы  регулярные выражения. Отладка их выполнена с помощью Построителя регулярных выражений.

В случае внесения изменений в эту обработку, вы получите оповещение. Настройка оповещений описана  в этой статье.

Похожие темы:

[Z-report] "Битва титанов v.1" Подбор продаж под сумму Z-отчета

Подбор слагаемых для нужной суммы

Желаю приятного просмотра!

Обновления

24.05.2017 12:00 - теперь, сколько бы мы не запустили серий попыток подбора значений, будем располагать лучшим результатом из всех найденных подборов.

25.05.2017 10:00 - выполнена небольшая оптимизация. Теперь, при программном вызове обработки, если сумма для подбора больше половины итоговой суммы исходного набора чисел, - выполняется подбор итоговой суммы за вычетом суммы для подбора (назовем дополнением к требуемой сумме). Ибо, подобрать меньшую сумму в среднем быстрее, чем большую, в моем разумении... Результат из обработки возвращается требуемый, разумеется. Возвращаемый из обработки набор чисел мы видим или в списке справа на форме, или в списке слева при подборе дополнения к сумме.

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    3230    stopa85    12    

38

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    7643    user1959478    52    

36

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    3165    maksa2005    8    

26

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    10940    7    SpaceOfMyHead    18    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    4422    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

В статье анализируются средства платформы для решения системы линейных уравнений в 1С. Приводятся доводы в пользу некорректной работы встроенных алгоритмов, а значит потенциально некорректного расчета себестоимости в типовых конфигурациях.

23.11.2022    3588    gzharkoj    14    

25

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    9052    7    kalyaka    11    

44
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. MSConfig 19.05.17 17:25 Сейчас в теме
Вот эту энергию и в мирное русло бы!
2. romasna 325 19.05.17 17:27 Сейчас в теме
(1)Не понял... что не так?
3. CheBurator 2712 19.05.17 17:39 Сейчас в теме
шпарит тупым перебором? или более интеллектуальные варианты решения задачи рбкзака применяются?
корум; starik-2005; +2 Ответить
5. romasna 325 19.05.17 17:44 Сейчас в теме
(3)Скачай и посмотри, пожалуйста, если интересно. Работает быстро. Из нескольких сотен случайных чисел подбирает сумму в среднем за 5сек. Надо только умело и творчески подойти к процессу. Не веришь - проверь. Генератор случайных чисел включен... Тупой перебор не выложил бы здесь - даже не стал бы позориться. ;) А энергию свою я употребил, когда потребовалось, на решение 3 разных задач. И в основе их - этот подбор сумм.
user1028159; +1 Ответить
6. romasna 325 19.05.17 17:48 Сейчас в теме
(3)О, пардон... это не ты пытался мою энергию в мирное русло направить... :)
10. romasna 325 19.05.17 18:12 Сейчас в теме
(3)Кстати, обращаю твое внимание на картинку к статье. Внизу строчка: требуемая сумма подобрана с первой попытки. На попытку не больше 20сек. было отведено. (Обычно, я и 20секунд не выставлял, а 5-10). Чисел для перебора около 140. Как ты знаешь, простой перебор за такое время результат не даст. На случайном наборе чисел все работает изумительно. Медленнее всего подбираются слишком маленькие и слишком большие (приграничные) суммы.
4. starik-2005 3088 19.05.17 17:41 Сейчас в теме
7. romasna 325 19.05.17 17:50 Сейчас в теме
(4)Лично я не против многообразия. Свои алгоритмы я программировал без шпаргалок. Что получилось - выложил. Мож кому понравятся. Денег не прошу. :) Я не перебираю все.
8. starik-2005 3088 19.05.17 17:54 Сейчас в теме
(7)
Денег не прошу. :) Я не перебираю в
1 стартмани стоит каких-никаких денег. Было бы интересно знать суть алгоритма. Фактически все условно быстрые алгоритмы не дают 100% точности кроме рюкзака. А рюкзак требует памяти (на каждую копейку до искомой суммы * количество сумм).
9. romasna 325 19.05.17 18:00 Сейчас в теме
(8)Стартмани стоят для нас с тобой только некоторых усилий... что-то разработал, выложил, получил... Или не так? Была бы моя воля, я бы и даром выложил эту обработку, - не жалко.
Что же до алгоритмов: большая часть суммы подбирается случайно (процент регулируешь ползунком), а потом - да, тупой перебор, но отбрасываются все тупиковые варианты. И если процесс длится долго, например, больше 20секунд, случайный набор чисел меняется на новый, если указано несколько попыток подбора.
11. CheBurator 2712 19.05.17 18:28 Сейчас в теме
интересует за сколько отработает алгоритм для ~100 разных подборов, на которых в каждом подборе ~15 чисел и они близки друг к другу
12. romasna 325 19.05.17 18:29 Сейчас в теме
(11)Полагаю, надо провести следственный эксперимент... давай набор чисел и требуемую сумму. Посмотрю.
13. CheBurator 2712 19.05.17 18:35 Сейчас в теме
так мне без разницы - что числа выдавать что смотреть... сам посмотрю если припрет.
а если припрет - придетяс из разработки выдирать колд, или там унутре есть функция на вход клоторой масив с данными - на выходе результат?
14. romasna 325 19.05.17 18:43 Сейчас в теме
(13)Вызываешь обработку модально, передав в нее список значений. Получив результат, давишь кнопку "Готово", - вываливаешься из обработки. На выходе в списке значений имеем требуемое. Задачи подобного рода я не решаю на полном автомате, - в меру своих умений вмешиваюсь в процесс получения результата. И обычно его получаю быстро, даже когда требуется полное совпадение с суммой.
Передается именно список значений, а не массив. Это позволяет решать задачи количественно-суммовые. Например, из остатков подобрать номенклатуру на заданную сумму в количестве и ценах.
В принципе, возможно все запускать на автомате, когда требуется сделать большое количество подборов. На вход подаешь не только массив чисел, но и указываешь длительность попытки подбора с неограниченным количеством попыток. Вот только я пока что не предусмотрел на этот случай выход из обработки по завершении подбора. Но это пустячное изменение алгоритмов.
15. jaroslav.h 180 21.05.17 15:44 Сейчас в теме
Ану подскажите, есть ТЧ дока, мне нужно из этой ТЧ выбрать коство шт. товару на определенную сумму, и я знаю, что эта сумма есть в этой тч, эта обработка такое решает?
16. romasna 325 21.05.17 16:03 Сейчас в теме
(15)И "да", и "нет". "Нет", - потому что эта обработка позволяет только сумму подобрать из имеющихся значений. Но также и "Да", потому что она лежит в основе решения твоей задачи. Вот только прежде чем перейти к подбору суммы по номенклатуре, необходимо до вызова обработки специальным образом обработать эту самую номенклатуру. Такой простой пример: есть у тебя 6 карандашей на сумму 24 рубля. В обработку передаешь несколько элементов по этим карандашам в списке значений:
12 - Карандаш 3шт.
8 - Карандаш 2шт.
4 - карандаш 1шт.
Эти 3 элемента позволяют набрать суммы; 4, 8, 12, 16, 20, 24
Допустим тебе нужна сумма 20. Эта обработка в списке значений вернет тебе 2 записи:
12 - Карандаш 3шт.
8 - Карандаш 2шт.
Обработав их, получишь: 5 карандашей на сумму 20.
jaroslav.h; +1 Ответить
17. Fanil 14.11.17 20:11 Сейчас в теме
отлично работает, когда необходимо подделать что-то в оборотке)))
18. romasna 325 16.11.17 11:25 Сейчас в теме
(17) Очень рад, что она тебе помогла нести светлое людям. :)
19. dndw 6 01.03.19 20:22 Сейчас в теме
Каким то образом можно ограничить выбор только определенным количеством элементов, т.е. чтобы сумма получалась как сумма только 5 (или любого другого числа) элементов из всего набора чисел?
20. romasna 325 03.03.19 11:45 Сейчас в теме
(19) Здравствуйте. Этой обработкой можно получить разные комбинации чисел на определенную заданием сумму. Можно, разве что, смотреть на то, что получилось по количеству чисел и выбирать подходящую комбинацию (программно, разумеется. Это не требует изменений обработки).
Или, найдите в коде то место, где анализируется промежуточный результат поиска и включите отказ от любого из них, которое не удовлетворяет Вашему дополнительному условию (уже много чисел!),- это может немного ускорить подбор. И это еще не все ускорение, которое можно получить... есть варианты. Но, на текущий момент такая функциональность не была предусмотрена.
21. dndw 6 04.03.19 11:08 Сейчас в теме
(20)
Или, найдите в коде то место, где анализируется промежуточный результат поиска и включите отказ от любого из них
Подскажите пожалуйста, где это происходит в коде.
23. romasna 325 04.03.19 13:07 Сейчас в теме
(21) Очевидно, что нужно ввести реквизит формы на количество слагаемых результата.

Функция ВыбратьСочетания (ИзЭн, ПоЭм) - запускает последовательность сочетаний ИзЭн ПоЭм; не трогаем.
Функция ПолучитьСочетание (Сочетание, ИзЭн, ПоЭм) - формирует следующее сочетание ИзЭн ПоЭм; не трогаем.
Изменения нужно внести в Процедура ОбработатьСочетание (Сочетание)
Сочетание - массив, количество элементов которого и есть количество слагаемых, которое нужно держать на контроле. Обращаю внимание, что в этой процедуре нарушается "нормальная" последовательность сочетаний, отсекаются заведомо не приводящие к нужному результату.

И это еще не все.
Процедура СлучайныйПодбор() - надо либо отказываться от случайного подбора, когда есть ограничение на к-во слагаемых, либо в него тоже внести поправки с учетом новых требований. И над этим нужно по-медитировать...
24. romasna 325 04.03.19 13:35 Сейчас в теме
(21) Меня только что осенило... надо ведь попросту рассмотреть только сочетания ИзЭн ПоЭм, когда ПоЭм равно требуемому количеству слагаемых за вычетом количества случайно подобранных. И тогда Процедура ОбработатьСочетание (Сочетание) - не трогаем. Все просто.
Понятное дело, в случайном подборе не может быть к-во слагаемых большее либо равное требуемому. Оно должно быть меньше, чтобы было еще что сочетать из оставшихся чисел.
22. romasna 325 04.03.19 12:18 Сейчас в теме
Могу я поинтересоваться, какую задачу Вы решаете? Для чего такое ограничение? Оно может весьма существенно увеличить время подбора...
25. dndw 6 04.03.19 15:39 Сейчас в теме
Сохранение количества и суммы при изменении цены.
28. romasna 325 04.03.19 22:45 Сейчас в теме
26. romasna 325 04.03.19 19:57 Сейчас в теме
Это совсем другого порядка задача. Предложенное мной выше решение - это совсем-совсем не то, что требуется. Я то полагал, что нужно подобрать сумму при фиксированном количестве слагаемых. В принципе, и это решение подойдет, если целочисленное количество и всю номенклатуру отдельными позициями подать в подбор, когда к-во равно 1. Да, так сработает.
27. dndw 6 04.03.19 20:59 Сейчас в теме
Что такое и планировал сделать развернуть все позиции до 1, и дальше составлять комбинацию.
	Сочетание = Новый Массив;
	Если ПоЭм <= ИзЭн
			Тогда 
			//Если ПоЭм =7 Тогда  /Где то в этом месте нужно вводить проверку?
	    Для Инд = 1 По ПоЭм Цикл
	        Сочетание.Добавить(Инд);
	    КонецЦикла;
		КонецЕсли;
	//КонецЕсли;
	Возврат Сочетание;
Показать
29. romasna 325 04.03.19 23:18 Сейчас в теме
(27) Еще раз... в подбор забрасываем всю номенклатуру: каждая строка подбора это отдельная (кво=1) позиция номенклатуры. Например, у нас 10 наименований по 5 штук каждого - итого 50 строк подбора (сумма каждой строки - это цена товара).
Модифицируем алгоритм. Сейчас рассматриваются все сочетания строк подбора:1 из 50; 2 из 50; 3 из 50; ... ; 49 из 50; 50 из 50. Цикл в цикле:
Сочетание = ВыбратьСочетания (ИзЭн, ПоЭм) ;
И в цикле: ПолучитьСочетание (Сочетание, ИзЭн, ПоЭм);
ОбработатьСочетание (Сочетание)

Например, нужно подобрать 13 позиций номенклатуры из 50 на некую заданную сумму. Что мы делаем?
1. случайно подбираем сколько-то. Например, 8.
2. Оставшиеся 5 получаем путем сочетаний из 42(ИзЭн) по 5(ИзЭм). Почему из 42, а не из 50? Да потому что 8 мы подобрали уже случайно. (Случайный подбор не нужно менять, - он регулируется на форме ползунком.)
В-общем, все самое сложное я уже сделал, а Вам осталось модифицировать несколько строк программного кода. Желаю удачи. :)
30. user1202287 13.04.19 15:33 Сейчас в теме
31. пользователь 19.11.21 08:32
Сообщение было скрыто модератором.
...
32. it@contlog.ru 20.05.22 03:18 Сейчас в теме
Нужно возможность добавить в список отрицательных чисел Будет работать? У нас порядка 1300 значений.
33. FarFar 47 09.08.24 20:17 Сейчас в теме
Открываю обработку, настройки по умолчанию. Входящие цифры (слева): 40; 34; 31; 10.4. Целевая 50. Перемещает вправо 34 и 31 (((( Не видит варианта 40 + 10.4
34. romasna 325 15.08.24 14:59 Сейчас в теме
(33) Здравствуйте, FarFar. Спасибо за пример. Сам я, честно говоря, не решал задачу на таком маленьком наборе чисел. А ведь добавь вы в него еще одно число, и уже не получили бы такой кривой результат, как сейчас. И да, - я его подтверждаю.

Алгоритм, заложенный в обработку, таки рассчитан на гораздо большее их (чисел) количество (сотни, тысячи). И потому, учитывая сложность поставленной задачи, надо было его сделать как можно более эффективным и по времени, и по точности подбора. Как показало время, работает он очень даже не плохо, я много раз тестировал его на случайных наборах чисел, - результат очень и очень хороший.

Разумеется, если бы мне надо было сделать подбор не более чем из 4 чисел, то я построил бы алгоритм, основанный на простом переборе. И выдал бы наиболее точный результат. А ведь с этого я и начинал: строил сочетания чисел, выбирал среди них наиболее подходящее, и очень скоро зашел в тупик, - никакого суперкомпьютера не будет достаточно для достижения цели, когда чисел много.

Наверное, в предположении,что чисел будет мало, стоит построить отдельную ветку алгоритма. И это будет самое простое решение. Я бы так и поступил...
35. FarFar 47 20.08.24 12:28 Сейчас в теме
(34) у нас этих чисел может быть от 2 до 30-40...
А на что влияет "Точность" в форме обработки? В данном примере ее изменение не помогает, какую ни ставь. Но в целом, хотелось бы знать. Как то не понял из описания обработки.
А так, хорошая обработка, понравилась.
36. romasna 325 30.08.24 14:33 Сейчас в теме
(35) Ползунок определяет часть суммы случайного подбора чисел. Т.е., вы можете большую часть требуемой суммы набрать случайным образом, а оставшуюся часть требуемой суммы подобрать с указанной точностью. Так следует поступать, когда чисел очень много, иначе будете ждать вечность свой результат. И чем больше у вас чисел, тем большую часть набирайте случайным образом. Замечу, что в случайный набор входят самые большие числа в первую очередь, а маленькие числа служат для уточнения результата с заданной точностью путем различных сочетаний этих чисел.
Если требуется строгий подбор чисел на <сумму>, точность подбора указывается равной нулю. Точность, другими словами, это допустимая разница по модулю от суммы подобранных чисел и требуемой суммой. Например, при точности 10 вы можете в результате получить числа подбора 5+7+14= 26, когда требовалось найти числа, дающие сумму 20, ибо: |20-26| = 6 < 10 (требуемой точности подбора). Работа алгоритма прерывается, когда достигнута указанная точность подбора. Наверно, было бы корректней назвать этот параметр <допустимым отклонением> от требуемой суммы, но вот как-то не догадался в свое время. :)
Не лишне ограничивать количество попыток подбора, когда присутствует случайный набор, и время одного цикла подбора. В зависимости от того, что удалось набрать случайным образом, оставшаяся часть может быть найдена за доли секунды, а иногда и часов не хватит на это. Тестирование на случайных наборах чисел показало, что обычно это занимает от одной до нескольких секунд.
В вашем случае подбор из 2-3 чисел вы можете и простым циклом организовать, а если больше 3 чисел, сработает эта обработка (я не заметил багов). Воспользуйтесь функциями для получения различных сочетаний чисел из ЭН по ЭМ, найдете их в модуле обработки. Для каждого сочетания вычисляйте сумму и выбирайте сочетание наиболее близкое требуемой сумме. Желаю успехов!
37. FarFar 47 13.09.24 09:46 Сейчас в теме
(36) Понятно. Тогда можно еще эту вашу точность сделать бы как в плюс, так и в минус. Иногда "больше можно, меньше нельзя".

Да, для своей практической задачи я скомбинировал. Если количество чисел в подборе <=9, то ищу оптимум своим алгоритмом (прямым перебором). Может я его удачно написал, но на выборке 9 чисел он работает мгновенно. Думаю, и больше можно задать. А если 10 и больше - то используется ваш.
Оставьте свое сообщение