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

19.05.17

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

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

Файлы

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

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

Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний

Оформите подписку на компанию для решения рабочих задач

Оформить подписку и скачать решение со скидкой

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

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

Ползунок в обл.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 1C:Бухгалтерия Россия Абонемент ($m)

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

1 стартмани

30.01.2024    8671    stopa85    12    

42

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

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

19.10.2023    14886    user1959478    57    

37

Математика и алгоритмы Разное 1С v8.3 1C:Бухгалтерия Россия Абонемент ($m)

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

2 стартмани

29.09.2023    8350    maksa2005    8    

27

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

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

1 стартмани

09.06.2023    16432    10    SpaceOfMyHead    20    

63

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

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

03.04.2023    9652    RustIG    9    

29

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

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

23.11.2022    8777    gzharkoj    15    

26

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

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

1 стартмани

21.03.2022    10202    8    kalyaka    11    

45

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

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    11001    fishca    12    

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

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

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

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

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

Наверное, в предположении,что чисел будет мало, стоит построить отдельную ветку алгоритма. И это будет самое простое решение. Я бы так и поступил...
35. FarFar 47 20.08.24 12:28 Сейчас в теме
(34) у нас этих чисел может быть от 2 до 30-40...
А на что влияет "Точность" в форме обработки? В данном примере ее изменение не помогает, какую ни ставь. Но в целом, хотелось бы знать. Как то не понял из описания обработки.
А так, хорошая обработка, понравилась.
36. romasna 326 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 и больше - то используется ваш.
Оставьте свое сообщение