Как сопоставить строки двух таблиц по количеству без разбиения строк в 1С?

← На главную

В практике разработчика 1С часто возникает задача синхронизации двух документов или таблиц значений (ТЗ), где данные в одной из таблиц были детализированы (например, разбиты по сериям, складам или аналогам). Типичный пример: имеется Заказ покупателя №1, который был уточнен и разбит на множество строк, и Заказ покупателя №2, где та же номенклатура указана укрупненно. Нам необходимо сопоставить строки так, чтобы каждой строке из первой таблицы соответствовала группа целых строк из второй таблицы, сумма которых точно равна исходному количеству. Главное условие — строки из второй таблицы нельзя «дробить».

С точки зрения математики и программирования, мы имеем дело с вариацией задачи о сумме подмножеств (Subset Sum Problem). Рассмотрим подробнее, как реализовать алгоритм решения этой задачи в среде 1С.

Анализ проблемы и классификация алгоритма

Проанализируем ситуацию: у нас есть две коллекции. В первой (ТЗ1) хранятся «целевые суммы», во второй (ТЗ2) — «слагаемые». Нам нужно распределить все слагаемые из ТЗ2 по «корзинам» из ТЗ1. Если бы строки можно было разбивать, мы бы использовали классический алгоритм ФИФО (нарастающий итог). Однако запрет на дробление превращает задачу в переборную, относящуюся к классу NP-полных.

Рассмотрим основные подходы к решению этой задачи, начиная от простых эвристик и заканчивая сложными методами перебора.

Метод 1: Предварительная фильтрация и «жадная» эвристика

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

Исключение полных совпадений: Найдем в ТЗ1 и ТЗ2 строки с абсолютно одинаковым количеством. Если такие пары найдены, мы сразу сопоставляем их и исключаем из дальнейшего рассмотрения.
Группировка по артикулу: Очевидно, что сопоставление имеет смысл только в рамках одной номенклатурной позиции (или группы аналогов). Разделим общую задачу на подзадачи для каждого артикула.
Сортировка по убыванию: Это критически важный шаг для любого переборного алгоритма. Начнем подбор с самых больших значений. Рассмотрим почему: большие числа гораздо труднее «втиснуть» в остаток суммы, поэтому, распределив их в первую очередь, мы быстрее поймем, возможна ли текущая ветка решения.

Метод 2: Рекурсивный перебор с возвратом (Backtracking)

Если после фильтрации остались сложные случаи, применим алгоритм с возвратом. Мы будем пытаться собрать сумму для первой строки ТЗ1, выбирая элементы из ТЗ2. Если сумма собрана — переходим к следующей строке ТЗ1. Если мы зашли в тупик (сумма не собирается, а элементы остались), мы возвращаемся на шаг назад и пробуем другую комбинацию элементов ТЗ2.

Посмотрим на пример логики функции, которая ищет комбинацию индексов:


Функция НайтиСочетание(ЦелеваяСумма, МассивСлагаемых, ТекущийИндекс = 0, ВыбранныеИндексы = Неопределено)
    Если ВыбранныеИндексы = Неопределено Тогда
        ВыбранныеИндексы = Новый Массив;
    КонецЕсли;

    Если ЦелеваяСумма = 0 Тогда
        Возврат Истина; // Сумма успешно собрана
    КонецЕсли;

    Для и = ТекущийИндекс По МассивСлагаемых.ВГраница() Цикл
        Слагаемое = МассивСлагаемых[и];
        
        Если Слагаемое.Использован Тогда
            Продолжить;
        КонецЕсли;
        
        Если Слагаемое.Значение <= ЦелеваяСумма Тогда
            // Пробуем включить это число в комбинацию
            Слагаемое.Использован = Истина;
            ВыбранныеИндексы.Добавить(Слагаемое.Индекс);
            
            Если НайтиСочетание(ЦелеваяСумма - Слагаемое.Значение, МассивСлагаемых, и + 1, ВыбранныеИндексы) Тогда
                Возврат Истина;
            КонецЕсли;
            
            // Если не подошло, делаем "откат" (backtrack)
            ВыбранныеИндексы.Удалить(ВыбранныеИндексы.Количество() - 1);
            Слагаемое.Использован = Ложь;
        КонецЕсли;
    КонецЦикла;

    Возврат Ложь;
КонецФункции

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

Метод 3: Использование битовых масок (для малых выборок)

Если количество строк в ТЗ2 для одного артикула не превышает 30, можно использовать мощный прием с битовыми масками. Каждому элементу ТЗ2 ставится в соответствие бит в числе. Пройдя циклом от 1 до 2^N, мы можем заранее вычислить все возможные суммы, которые можно собрать из элементов ТЗ2, и сохранить их в Соответствие, где ключом будет сумма, а значением — массив масок.

Проанализируем преимущества этого метода:

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

Метод 4: Решение через SQL-запрос (Cross Join)

В некоторых случаях задачу можно решить прямо в запросе 1С, если мы заранее знаем максимальное количество слагаемых (например, не более 3-х строк ТЗ2 на одну строку ТЗ1). Выясним причину эффективности этого метода: база данных оптимизирует соединения таблиц гораздо лучше, чем интерпретатор встроенного языка.

Пример структуры такого запроса:


ВЫБРАТЬ
    ТЗ1.НомерСтроки КАК НомерТЗ1,
    ТЗ2_1.НомерСтроки КАК Индекс1,
    ТЗ2_2.НомерСтроки КАК Индекс2,
    ТЗ2_3.НомерСтроки КАК Индекс3
ИЗ
    ВТ_ТЗ1 КАК ТЗ1
    ЛЕВОЕ СОЕДИНЕНИЕ ВТ_ТЗ2 КАК ТЗ2_1 ПО ТЗ1.Артикул = ТЗ2_1.Артикул
    ЛЕВОЕ СОЕДИНЕНИЕ ВТ_ТЗ2 КАК ТЗ2_2 ПО ТЗ1.Артикул = ТЗ2_2.Артикул И ТЗ2_1.НомерСтроки < ТЗ2_2.НомерСтроки
    ЛЕВОЕ СОЕДИНЕНИЕ ВТ_ТЗ2 КАК ТЗ2_3 ПО ТЗ1.Артикул = ТЗ2_3.Артикул И ТЗ2_2.НомерСтроки < ТЗ2_3.НомерСтроки
ГДЕ
    (ЕСТЬNULL(ТЗ2_1.Кол, 0) + ЕСТЬNULL(ТЗ2_2.Кол, 0) + ЕСТЬNULL(ТЗ2_3.Кол, 0)) = ТЗ1.Кол

Важное ограничение: этот метод подходит только для поиска одного сочетания. Если нужно распределить все строки ТЗ2 между всеми строками ТЗ1, запрос станет слишком громоздким и неэффективным.

Практические рекомендации

Подведем итоги и сформируем оптимальный план действий для реализации алгоритма:

Сортируйте данные. Всегда начинайте с самых крупных сумм в ТЗ1 и самых крупных слагаемых в ТЗ2.
Кэшируйте результаты. Если одна и та же сумма встречается в ТЗ1 несколько раз, не вычисляйте её заново, а попробуйте использовать уже найденные комбинации (с учетом доступности строк ТЗ2).
Добавляйте уникальные ключи. Чтобы не запутаться в индексах при рекурсии, добавьте в ТЗ2 служебную колонку КлючСтроки (например, через Новый УникальныйИдентификатор()), это упростит отметку «использованных» строк.
Контролируйте итоги. После завершения работы алгоритма обязательно сверьте общую сумму распределенных строк ТЗ2 с общей суммой ТЗ1. Они должны совпадать до копейки.

Рассмотренные подходы позволяют решить задачу сопоставления строк в 95% случаев бизнес-практики. В оставшихся 5% (когда данных слишком много и перебор зависает) рекомендуется либо пересмотреть бизнес-логику (почему связь была потеряна?), либо разрешить пользователю ручную корректировку результатов алгоритма.