Как найти все комбинации строк документа, сумма которых равна заданному значению, в 1С?

← На главную

При работе с данными в 1С часто возникает задача, когда необходимо найти определенные комбинации числовых значений (например, сумм строк документа), которые в совокупности дают требуемую целевую сумму. Это может быть актуально для различных сценариев: подбор платежей, формирование комплектов, анализ распределения бюджета и многое другое. На первый взгляд, такая задача может показаться связанной с обходом графов, однако по своей сути она является классической комбинаторной проблемой, известной как задача о сумме подмножеств (Subset Sum Problem), которая тесно связана с более общей задачей о рюкзаке (Knapsack Problem).

Суть задачи заключается в следующем: у нас есть набор чисел (например, суммы из строк документа) и целевая сумма. Нам необходимо найти одно или несколько подмножеств этих чисел, сумма которых в точности равна целевой. Если порядок элементов не важен, мы ищем подмножества (сочетания). Если же важен порядок или каждый элемент уникален и не может быть использован повторно, мы можем говорить о перестановках.

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

Понимание сложности задачи: NP-полнота и экспоненциальный рост

Прежде чем погружаться в конкретные алгоритмы, очень важно осознать сложность задачи. Задача о сумме подмножеств является NP-полной. Это означает, что для нее не существует известных полиномиальных алгоритмов, которые гарантированно найдут решение за разумное время при значительном увеличении количества исходных чисел (элементов). Число возможных подмножеств из N элементов равно 2^N (если учитывать пустое подмножество, или 2^N - 1, если нет). Давайте представим, насколько быстро растет это число:

Для N = 10, у нас будет 2^10 = 1024 варианта.
Для N = 20, это уже 2^20 = 1 048 576 вариантов.
Для N = 30, мы получаем 2^30 ≈ 1 миллиард вариантов (1 073 741 824).

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

Рекурсивный полный перебор вариантов в 1С

Один из самых прямолинейных способов решить эту задачу — использовать полный перебор (brute-force), который удобно реализовать с помощью рекурсии. Каждый элемент из исходного набора может быть либо включен в текущее подмножество, либо нет. Такой подход естественно ложится на рекурсивную структуру.

Давайте сначала вспомним классический пример рекурсии в 1С — вычисление факториала:


Функция Факториал(N)
    Если N = 1 Тогда
        Возврат 1;
    Иначе
        Возврат N * Факториал(N - 1);
    КонецЕсли;
КонецФункции

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

Общая логика рекурсивного перебора для задачи о сумме подмножеств выглядит так:

Определяем базовый случай:
- Если текущая сумма равна целевой, мы нашли решение. Записываем его.
- Если мы перебрали все элементы или текущая сумма превысила целевую, итерацию прекращаем.
Для каждого элемента на текущем уровне рекурсии:
- Включаем элемент в текущее подмножество, добавляем его к текущей сумме и вызываем рекурсию для следующего элемента.
- Исключаем элемент из текущего подмножества и вызываем рекурсию для следующего элемента.

Важные моменты для 1С:

Глубина рекурсии: 1С поддерживает рекурсивные вызовы, но слишком глубокая рекурсия (для больших N) может привести к переполнению стека и ошибкам. Необходимо внимательно следить за этим.
Производительность: Как обсуждалось, для N > 20 такой подход становится крайне медленным.
Передача параметров: Передача больших массивов или таблиц значений по значению в рекурсивные вызовы может быть накладной. Используйте ссылки или передавайте минимально необходимый контекст.

Для повышения эффективности рекурсивного перебора часто используют методы отсечения (backtracking или branch and bound). Принцип заключается в том, что если текущая накопленная сумма уже превышает целевую, или если даже с учетом всех оставшихся элементов невозможно достичь целевой суммы (например, текущая сумма + сумма всех оставшихся элементов меньше целевой), то эта ветвь перебора отбрасывается. Это позволяет значительно сократить количество проверяемых вариантов. Для такой оптимизации полезно предварительно отсортировать исходный массив чисел.

Динамическое программирование для задачи о сумме подмножеств

Для решения задачи о сумме подмножеств, особенно когда значения сумм и количество элементов ограничены, динамическое программирование (ДП) является одним из наиболее эффективных подходов. Он не перебирает все 2^N подмножества, а строит решение "снизу вверх", используя уже вычисленные результаты.

Алгоритм динамического программирования для задачи о сумме подмножеств обычно создает булеву таблицу dp[s] (или dp[i][s], где i — количество элементов, s — целевая сумма). Например, dp[s] будет истинным, если сумма s может быть получена из подмножества элементов, рассмотренных на текущем шаге. Итеративно мы проходим по всем элементам и обновляем нашу таблицу.

Общий подход к динамическому программированию:

Создаем булев массив (или Массив в 1С) dp размером TargetSum + 1. Инициализируем dp[0] = Истина (сумму 0 всегда можно получить, не выбирая ни одного элемента), остальные элементы Ложь.
Для каждого числа num в нашем исходном массиве:
- Перебираем возможные суммы s от TargetSum до num (в обратном порядке, чтобы избежать повторного использования того же числа в рамках одного шага):
- Если dp[s - num] истинно, то это означает, что сумму s - num можно было получить. Тогда, добавив num, мы можем получить сумму s. Устанавливаем dp[s] = Истина.
После обработки всех чисел, dp[TargetSum] покажет, можно ли получить целевую сумму.

Для того чтобы не только узнать, можно ли получить сумму, но и какие элементы ее формируют, нам потребуется хранить дополнительную информацию в таблице ДП (например, ссылки на предыдущие состояния или сами элементы). Это усложнит структуру, но является реализуемым.

Сложность такого подхода: составляет O(N * TargetSum), где N — количество элементов, а TargetSum — целевая сумма. Этот подход значительно эффективнее полного перебора, если TargetSum не слишком велико.

В 1С это может быть реализовано с использованием Массив для хранения булевых значений или ТаблицаЗначений для более сложного хранения информации о слагаемых. Однако, если TargetSum очень велика, то и этот метод может столкнуться с ограничениями по памяти и времени.

Генерация комбинаций через запросы 1С с CROSS JOIN (подход автора)

Автор ветки предложил интересный способ генерации всех возможных "путей/цепей" с использованием динамически формируемого запроса с CROSS JOIN (декартовым произведением). Этот подход предназначен для получения всех перестановок уникальных чисел из исходного массива, где каждый номер строки используется ровно один раз. Давайте рассмотрим его подробнее.

Функция 1С, предложенная автором:


&НаСервереБезКонтекста
Функция ПолучитьВсеВарианты(МассивСвободныеВершины, МассивЭталон)
    
    ТекстШаблон = "ВЫБРАТЬ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        Если ИндексМассива = 0 Тогда
            ТекстШаблон = ТекстШаблон + Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=");
        Иначе
            ТекстШаблон = ТекстШаблон + " ВЫБРАТЬ "+ Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=");
        КонецЕсли;
        
        Если ИндексМассива = 0 Тогда
            ТекстШаблон = ТекстШаблон + Символы.ПС +" КАК Символ ПОМЕСТИТЬ ТаблицаВершин ";
        КонецЕсли;
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + Символы.ПС + " ОБЪЕДИНИТЬ ВСЕ ";
        Иначе
            ТекстШаблон = ТекстШаблон + Символы.ПС + " ; ";
        КонецЕсли;
        
    КонецЦикла;
    
    ТекстШаблон = ТекстШаблон + " ВЫБРАТЬ * ИЗ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + " ТаблицаВершин КАК ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ ", ";
        Иначе
            ТекстШаблон = ТекстШаблон + " ТаблицаВершин КАК ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ " ";
        КонецЕсли;
        
    КонецЦикла;
    
    ТекстШаблон = ТекстШаблон + Символы.ПС + "ГДЕ ";
    
    Для ИндексМассива = 0 По МассивСвободныеВершины.Количество() - 1 Цикл
        
        ТекстШаблон = ТекстШаблон + " НЕ ТаблицаВершин" +Формат(МассивСвободныеВершины[ИндексМассива], "ЧГ=")+ ".Символ В ( ";
        Для ИндексЭталон = 0 По МассивЭталон.Количество() - 1 Цикл
            
            Если ИндексЭталон = МассивЭталон.Количество() - 1 И ИндексМассива = МассивСвободныеВершины.Количество() - 1 Тогда
                ТекстШаблон = Лев(ТекстШаблон, СтрДлина(ТекстШаблон) - 2) + ") ";
                Продолжить;
            ИначеЕсли ИндексЭталон = ИндексМассива Тогда
                Продолжить;
            КонецЕсли;
            
            Если ИндексЭталон <> МассивЭталон.Количество() - 1 Тогда
                ТекстШаблон = ТекстШаблон + " ТаблицаВершин" +Формат(МассивЭталон[ИндексЭталон], "ЧГ=")+ ".Символ, ";
            Иначе
                ТекстШаблон = ТекстШаблон + " ТаблицаВершин" +Формат(МассивЭталон[ИндексЭталон], "ЧГ=")+ ".Символ) ";
            КонецЕсли;
            
        КонецЦикла;
        
        Если ИндексМассива <> МассивСвободныеВершины.Количество() - 1 Тогда
            ТекстШаблон = ТекстШаблон + " И ";
        КонецЕсли;
        
    КонецЦикла;
    
    ЗапросПути = Новый Запрос;
    ЗапросПути.Текст = ТекстШаблон;
    
    АутКам = ЗапросПути.Выполнить().Выгрузить();
     Возврат АутКам;
    
КонецФункции

Данная функция генерирует SQL-запрос, который создает временную таблицу ТаблицаВершин из уникальных значений переданного массива. Затем она выполняет CROSS JOIN этой таблицы саму с собой столько раз, сколько элементов в массиве. Условие ГДЕ НЕ ТаблицаВершинX.Символ В (ТаблицаВершинY.Символ, ...) предназначено для исключения комбинаций, где одна и та же "вершина" (число) используется более одного раза в рамках одной "цепи".

Пример сгенерированного запроса для чисел 9, 10, 11, 12:


 ВЫБРАТЬ 9
 КАК Символ ПОМЕСТИТЬ ТаблицаВершин 
 ОБЪЕДИНИТЬ ВСЕ   ВЫБРАТЬ 10
 ОБЪЕДИНИТЬ ВСЕ   ВЫБРАТЬ 11
 ОБЪЕДИНИТЬ ВСЕ   ВЫБРАТЬ 12
 ;   ВЫБРАТЬ * ИЗ   ТаблицаВершин КАК ТаблицаВершин9,   ТаблицаВершин КАК ТаблицаВершин10,   ТаблицаВершин КАК ТаблицаВершин11,   ТаблицаВершин КАК ТаблицаВершин12 
ГДЕ   НЕ ТаблицаВершин9.Символ В (   ТаблицаВершин10.Символ,   ТаблицаВершин11.Символ,   ТаблицаВершин12.Символ)   И   НЕ ТаблицаВершин10.Символ В (   ТаблицаВершин9.Символ,   ТаблицаВершин11.Символ,   ТаблицаВершин12.Символ)   И   НЕ ТаблицаВершин11.Символ В (   ТаблицаВершин9.Символ,   ТаблицаВершин10.Символ,   ТаблицаВершин12.Символ)   И   НЕ ТаблицаВершин12.Символ В (   ТаблицаВершин9.Символ,   ТаблицаВершин10.Символ,   ТаблицаВершин11.Символ)

Ограничения и соображения производительности:

Экспоненциальный рост результата: Количество строк в результате CROSS JOIN растет экспоненциально (N^K, где N - количество уникальных элементов, K - количество таблиц). Для поиска сочетаний или подмножеств, это приводит к генерации огромного количества данных, которые затем фильтруются.
Ограничения SQL: Современные СУБД имеют лимиты на количество таблиц в JOIN-операции. При большом количестве элементов (скажем, более 10-15), такой запрос может не выполниться вовсе или будет работать крайне медленно.
Применимость: Данный подход больше подходит для генерации перестановок (последовательностей) заданной длины из уникальных элементов, а не для поиска подмножеств с целевой суммой произвольной длины. Для задачи о сумме подмножеств это не самый прямой и эффективный метод.

Жадный алгоритм (Greedy Algorithm)

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

Сначала мы упорядочиваем все числа в массиве, например, по убыванию.
Затем мы начинаем итеративно добавлять числа к текущей сумме. Если текущая накопленная сумма все еще меньше целевой, мы добавляем следующее число. Если она превысила целевую, мы пропускаем это число и переходим к следующему.

Пример: Целевая сумма 100, числа: 50, 40, 30, 20, 10.

Берем 50 (сумма 50).
Берем 40 (сумма 90).
Берем 30 (сумма 120) — превысила 100, пропускаем.
Берем 20 (сумма 110) — превысила 100, пропускаем.
Берем 10 (сумма 100). Нашли одну комбинацию: 50 + 40 + 10 = 100.

Ограничения жадного алгоритма:

Неоптимальность: Жадный алгоритм не гарантирует нахождение всех решений или даже оптимального решения (если цель — минимизировать количество элементов). Он находит только одно решение, которое формируется по строго определенным правилам. Например, если 50+40+10=100 и 30+20+50=100, жадный алгоритм, стартующий с 50, мог бы не найти вторую комбинацию.
Отрицательные числа: Если в массиве присутствуют отрицательные числа, жадный алгоритм становится еще менее предсказуемым и может не сработать корректно без дополнительных модификаций.

Случайный алгоритм (Randomized Algorithm)

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

Общая идея:

Начинаем с произвольного подмножества чисел (например, пустого или случайного).
Вычисляем текущую сумму.
Если сумма меньше целевой, случайным образом добавляем одно число из оставшихся.
Если сумма больше целевой, случайным образом удаляем одно число из текущего подмножества.
Повторяем процесс до тех пор, пока не достигнем целевой суммы (или не приблизится к ней в пределах допустимой погрешности).

Более сложный вариант с несколькими массивами (как предложено в обсуждении):

Используем четыре массива:
- Два массива для чисел, которые уже вошли в текущую сумму: один для положительных чисел, другой для отрицательных.
- Два других массива для чисел, которые еще не вошли в сумму (свободные): один для положительных, другой для отрицательных.
Изначально заполняем два "свободных" массива всеми числами.
Если текущая сумма меньше, чем целевая:
- Случайно выбираем число из "свободных" массивов.
- Если выбранное число отрицательное, мы, возможно, должны добрать из "свободного" положительного массива несколько случайных чисел, чтобы итог был положительным или более близким к целевому.
- Переносим выбранное число (и, возможно, дополнительные) в соответствующие массивы "в сумме".
Если текущая сумма больше, чем целевая:
- Случайно выкидываем число из двух массивов "в сумме".
- Если выкинутое число отрицательное, возможно, нужно добавить из "свободного" положительного массива, чтобы скорректировать сумму.
- Переносим выкинутое число в соответствующие "свободные" массивы.
Гоняем алгоритм, пока не получим нужную сумму или не исчерпаем попытки.

Этот подход может быть настроен с допустимой погрешностью, если точное совпадение не является обязательным.

Использование внешних сервисов (Python)

Когда задача становится слишком сложной для эффективной реализации в 1С (из-за производительности, объема данных или сложности алгоритма), одним из наиболее практичных решений является вынесение расчетов во внешний сервис. Языки программирования, такие как Python, предлагают обширные библиотеки для численных расчетов (например, NumPy, SciPy) и решения комбинаторных задач, включая реализацию различных алгоритмов для задачи о рюкзаке и сумме подмножеств.

Преимущества:

Высокая производительность: Python (с соответствующими библиотеками) значительно быстрее обрабатывает сложные вычисления, чем 1С.
Готовые решения: Существует множество библиотек и примеров кода для стандартных алгоритмических задач.
Масштабируемость: Внешний сервис может быть развернут на отдельном мощном сервере и масштабироваться независимо от сервера 1С.

Интеграция с 1С:

Интеграция с такими сервисами может быть реализована различными способами:

Веб-сервисы (SOAP/REST): 1С может вызывать HTTP-сервисы (REST API) или SOAP-веб-сервисы, предоставляемые внешним приложением. Это стандартный и гибкий способ обмена данными.
HTTP-запросы: Для более простых взаимодействий можно использовать объекты 1С HTTPЗапрос и HTTPСоединение для отправки данных и получения результатов.
Внешние компоненты: Для максимальной производительности и прямого взаимодействия можно разработать внешнюю компоненту 1С на C++ или другом языке, которая будет вызывать Python-код (через C API или другие механизмы).

Этот подход позволяет использовать мощь специализированных алгоритмов, не перегружая функционал 1С, и является рекомендуемым для критически важных по производительности или сложности задач.

Общие рекомендации по разработке в 1С

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

Основные принципы:

Упрощение: Всегда спрашивайте себя, можно ли решить задачу более простыми циклами и элементарными арифметическими расчетами, даже если теоретически она кажется сложной. Часто бизнес-требования позволяют применять эвристики или приближенные решения, которые значительно проще реализуются.
Понятность кода: Избегайте "наркомании" и излишних нагромождений сложного кода, имитирующего продвинутую математику, если это не оправдано. Код должен быть читаемым и поддерживаемым другими программистами 1С, которые могут не обладать глубокими знаниями в теории алгоритмов.
Фокус на бизнес-логике: Например, если задача — уложиться в бюджет, подбирая премии с учетом налогов (как в одном из примеров из обсуждения), то простой итеративный пересчет с корректировкой коэффициентов может быть гораздо эффективнее, чем попытки строить сложные графы или решать задачи оптимизации формальными методами.
Асинхронные операции: Для длительных вычислений используйте фоновые задания. Это позволит не блокировать интерфейс пользователя и равномерно распределить нагрузку на сервер.

Поиск статей и материалов по графам в 1С (Ильдарович)

В рамках обсуждения было упомянуто имя "Ильдарович" как автора интересных статей по графам и их обходу в 1С. Если вы хотите углубиться в тему построения и обхода произвольных графов непосредственно средствами 1С, то можете найти его материалы на площадках, таких как Infostart. Ищите публикации по автору "ildarovich". В его статьях можно найти примеры:

Построение произвольного графа.
Обход графа различными методами (например, в ширину, в глубину).
Применение запросов 1С для решения задач, связанных с графами.

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

Выбирая метод решения, всегда начинайте с анализа объема данных, допустимой погрешности и требуемой производительности. Для небольших объемов простой рекурсивный перебор может быть достаточным. Для больших — рассмотрите динамическое программирование или использование внешних высокопроизводительных сервисов.