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

19.05.17

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

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

Скачать файлы

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

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

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

Ползунок в обл.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    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

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

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

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

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

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

1 стартмани

09.06.2023    7455    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

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

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

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

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

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

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

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

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

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

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

31.08.2021    7797    dusha0020    8    

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

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

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