В практике разработчика 1С периодически возникают нетривиальные алгоритмические задачи. Одна из них — необходимость перебрать все возможные комбинации строк из нескольких таблиц значений, когда количество этих таблиц заранее неизвестно (динамический массив из N элементов). Математически эта задача называется нахождением декартова произведения множеств.
В этой статье мы подробно разберем, почему стандартные вложенные циклы не подходят для динамических условий, и детально изучим три надежных способа реализации этой задачи в среде «1С:Предприятие 8»: с помощью рекурсии, динамического запроса и итеративного алгоритма без рекурсии.
Представим, что у нас есть массив, содержащий N таблиц значений. В каждой таблице есть колонка Сумма. Нам нужно выбрать ровно по одной строке из каждой таблицы значений так, чтобы сумма выбранных показателей равнялась определенному числу (например, 5). При этом количество строк в каждой таблице может быть абсолютно разным.
Если бы мы точно знали, что таблиц всегда три, мы бы написали простой код с тремя вложенными циклами:
Для Каждого СтрокаТаблицы0 из МассивТЗ[0] Цикл
Для Каждого СтрокаТаблицы1 из МассивТЗ[1] Цикл
Для Каждого СтрокаТаблицы2 из МассивТЗ[2] Цикл
ВВ = СтрокаТаблицы0.Сумма + СтрокаТаблицы1.Сумма + СтрокаТаблицы2.Сумма;
Если ВВ = 5 Тогда
Сообщить("Найдена комбинация!");
КонецЕсли;
КонецЦикла;
КонецЦикла;
КонецЦикла;
Но что делать, если в массиве может оказаться 2, 5, 10 или N таблиц значений? Написать статичные вложенные циклы в таком случае невозможно. Нам нужен универсальный и масштабируемый код. Ниже мы детально разберем три отличных решения этой проблемы.
Рекурсия — это наиболее естественный способ реализации вложенных циклов произвольной глубины. Мы будем последовательно «погружаться» на каждый следующий уровень массива таблиц значений, передавая накопленные данные дальше по стеку вызовов.
Давайте разработаем универсальную процедуру рекурсивного обхода. Мы будем передавать в нее текущий индекс таблицы из массива и уже накопленную сумму на предыдущих шагах. Это позволит нам применить важную оптимизацию: если суммы чисел только положительные и текущая сумма превысила лимит, мы можем досрочно прервать ветку вычислений (метод ветвей и границ).
Проанализируем пример кода с рекурсией:
// Основная процедура, запускающая расчет
Процедура ВыполнитьПоискКомбинаций(МассивТЗ)
Если МассивТЗ.Количество() = 0 Тогда
Возврат;
КонецЕсли;
// Создадим структуру для передачи сквозных параметров (например, результатов)
ПараметрыОбхода = Новый Структура;
ПараметрыОбхода.Вставить("ЦелеваяСумма", 5);
ПараметрыОбхода.Вставить("НайденныеВарианты", Новый Массив);
// Вспомогательный массив для хранения индексов выбранных строк на каждом шаге
ВыбранныеСтроки = Новый Массив;
Для Сч = 1 По МассивТЗ.Количество() Цикл
ВыбранныеСтроки.Добавить(Неопределено);
КонецЦикла;
// Запуск рекурсивного обхода с 0-го уровня (первая таблица в массиве)
РекурсивныйОбходТаблиц(МассивТЗ, 0, 0, ВыбранныеСтроки, ПараметрыОбхода);
Сообщить("Поиск завершен. Найдено комбинаций: " + ПараметрыОбхода.НайденныеВарианты.Количество());
КонецПроцедуры
// Рекурсивный обработчик
Процедура РекурсивныйОбходТаблиц(МассивТЗ, ТекущийИндексТЗ, ТекущаяСумма, ВыбранныеСтроки, ПараметрыОбхода)
// Базовое условие выхода из рекурсии: мы дошли до конца массива
Если ТекущийИндексТЗ = МассивТЗ.Количество() Тогда
Если ТекущаяСумма = ПараметрыОбхода.ЦелеваяСумма Тогда
// Сохраняем успешную комбинацию индексов строк
ПараметрыОбхода.НайденныеВарианты.Добавить(Новый Массив(ВыбранныеСтроки));
Сообщить("Найдена комбинация индексов строк: " + ПолучитьСтрокуИндексов(ВыбранныеСтроки));
КонецЕсли;
Возврат;
КонецЕсли;
// Оптимизация: если числа неотрицательные и сумма уже больше лимита, выходим раньше
Если ТекущаяСумма > ПараметрыОбхода.ЦелеваяСумма Тогда
Возврат;
КонецЕсли;
ТекущаяТЗ = МассивТЗ[ТекущийИндексТЗ];
// Цикл по всем строкам текущей таблицы значений
Для ИндексСтроки = 0 По ТекущаяТЗ.Количество() - 1 Цикл
СтрокаТЗ = ТекущаяТЗ[ИндексСтроки];
// Запоминаем выбор текущей строки
ВыбранныеСтроки[ТекущийИндексТЗ] = ИндексСтроки;
// Шаг рекурсии: увеличиваем индекс таблицы на 1 и прибавляем сумму строки
РекурсивныйОбходТаблиц(МассивТЗ, ТекущийИндексТЗ + 1, ТекущаяСумма + СтрокаТЗ.Сумма, ВыбранныеСтроки, ПараметрыОбхода);
КонецЦикла;
КонецПроцедуры
Функция ПолучитьСтрокуИндексов(МассивИндексов)
Результат = "";
Для Каждого Значение Из МассивИндексов Цикл
Результат = Результат + ?(Результат = "", "", "-") + СокрЛП(Значение);
КонецЦикла;
Возврат Результат;
КонецФункции
Преимущества рекурсии: Код получается очень компактным, лаконичным и легким для чтения. Мы можем легко внедрять сложные правила отсечения неперспективных ветвей на ранних этапах погружения, что колоссально экономит ресурсы процессора.
Как совершенно справедливо заметили опытные разработчики в теме обсуждения, СУБД оптимизирована для работы с множествами гораздо лучше, чем встроенный язык 1С. Мы можем поместить все наши таблицы значений во временные таблицы (ВТ) внутри запроса, а затем выполнить их декартово произведение (полное соединение без указания условий связи).
Поскольку количество таблиц у нас динамическое, мы будем формировать текст запроса динамически в цикле. Давайте разберем этот мощный подход по шагам:
Функция НайтиКомбинацииЧерезЗапрос(МассивТЗ, ЦелеваяСумма)
Запрос = Новый Запрос;
МВТ = Новый МенеджерВременныхТаблиц;
Запрос.МенеджерВременныхТаблиц = МВТ;
ТекстПомещенияВТ = "";
СелекторПолей = "ВЫБРАТЬ ";
ИсточникДанных = " ИЗ ";
Для Индекс = 0 По МассивТЗ.Количество() - 1 Цикл
ИмяВТ = "ВТ_Таблица_" + Формат(Индекс, "ЧГ=0");
ИмяПараметра = "Параметр_" + Формат(Индекс, "ЧГ=0");
// Передаем ТЗ из массива в качестве параметра запроса
Запрос.УстановитьПараметр(ИмяПараметра, МассивТЗ[Индекс]);
// Строим текст создания временных таблиц с индексацией строк
ТекстПомещенияВТ = ТекстПомещенияВТ +
"ВЫБРАТЬ Автономер, Сумма ПОМЕСТИТЬ " + ИмяВТ + " ИЗ &" + ИмяПараметра + " КАК " + ИмяВТ + "_Исх;" + Символы.ПС;
// Формируем поля выборки (суммируем поля "Сумма" из всех ВТ и вытягиваем их автономера)
СелекторПолей = СелекторПолей + ?(Индекс > 0, " + ", "") + ИмяВТ + ".Сумма";
// Формируем источники (перечисление таблиц через запятую означает CROSS JOIN в SQL)
ИсточникДанных = ИсточникДанных + ?(Индекс > 0, ", ", "") + ИмяВТ + " КАК " + ИмяВТ;
КонецЦикла;
// Дополняем селектор псевдонимом результирующего поля
СелекторПолей = СелекторПолей + " КАК ИтоговаяСумма";
// Нам также важно знать, какие именно строки сформировали успешную комбинацию
Для Индекс = 0 По МассивТЗ.Количество() - 1 Цикл
ИмяВТ = "ВТ_Таблица_" + Формат(Индекс, "ЧГ=0");
СелекторПолей = СелекторПолей + ", " + ИмяВТ + ".Автономер КАК НомерСтроки_" + Формат(Индекс, "ЧГ=0");
КонецДля;
// Собираем итоговый текст запроса
ИтоговыйТекстЗапроса = ТекстПомещенияВТ + СелекторПолей + ИсточникДанных + " ГДЕ (" + СтрЗаменить(СелекторПолей, " КАК ИтоговаяСумма", "") + ") = &ЦелеваяСумма";
Запрос.Текст = ИтоговыйТекстЗапроса;
Запрос.УстановитьПараметр("ЦелеваяСумма", ЦелеваяСумма);
РезультатЗапроса = Запрос.Выполнить();
Если Не РезультатЗапроса.Пустой() Тогда
Возврат РезультатЗапроса.Выгрузить();
Иначе
Возврат Неопределено;
КонецЕсли;
КонецФункции
Для корректной работы этого алгоритма крайне важно, чтобы в исходных таблицах значений присутствовала колонка уникального идентификатора или автономера строки (например, Автономер), чтобы после выполнения запроса мы могли четко определить, какие именно строки составили комбинацию.
Преимущества метода запросов: Скорость работы на небольших объемах данных поражает, так как всю математику берет на себя СУБД. Нам не нужно писать сложные рекурсивные функции во встроенном языке.
Существует еще один профессиональный подход, который позволяет полностью избежать рекурсии (что исключает даже теоретический риск переполнения стека вызовов) и обойтись без использования механизма запросов. Мы можем эмулировать работу вложенных циклов с помощью массива состояний индексов.
Идея заключается в том, что мы создаем массив чисел размером N (где N — количество ТЗ), в котором каждый элемент хранит текущий индекс строки соответствующей таблицы. Затем мы вручную увеличиваем индекс последней таблицы. Если он выходит за допустимые пределы, мы сбрасываем его в 0 и переносим единицу в предыдущий разряд. Этот метод полностью аналогичен работе счетчика электроэнергии или прибавлению единицы в позиционной системе счисления с переменным основанием.
Проанализируем этот алгоритм на практике:
Процедура ОбходИтерационнымПутем(МассивТЗ, ЦелеваяСумма)
КоличествоТЗ = МассивТЗ.Количество();
Если КоличествоТЗ = 0 Тогда
Возврат;
КонецЕсли;
// 1. Создаем и инициализируем массив индексов для каждой таблицы
ТекущиеИндексы = Новый Массив;
Для Сч = 0 По КоличествоТЗ - 1 Цикл
ТекущиеИндексы.Добавить(0);
КонецЦикла;
Пока Истина Цикл
// 2. Считаем сумму по текущей комбинации индексов
ВременнаяСумма = 0;
Для Сч = 0 По КоличествоТЗ - 1 Цикл
ВременнаяСумма = ВременнаяСумма + МассивТЗ[Сч][ТекущиеИндексы[Сч]].Сумма;
КонецЦикла;
// Проверяем условие
Если ВременнаяСумма = ЦелеваяСумма Тогда
Сообщить("Найдена комбинация итерационным путем по индексам строк!");
КонецЕсли;
// 3. Шаг инкремента (двигаемся с последней таблицы к первой)
ИндексСдвига = КоличествоТЗ - 1;
Пока ИндексСдвига >= 0 Цикл
РазмерТекущейТЗ = МассивТЗ[ИндексСдвига].Количество();
// Если мы можем увеличить индекс в текущем разряде — увеличиваем и выходим из сдвига
Если ТекущиеИндексы[ИндексСдвига] < РазмерТекущейТЗ - 1 Тогда
ТекущиеИндексы[ИндексСдвига] = ТекущиеИндексы[ИндексСдвига] + 1;
Прервать;
Иначе
// Иначе сбрасываем текущий разряд в 0 и переносим инкремент на разряд левее (ИндексСдвига - 1)
ТекущиеИндексы[ИндексСдвига] = 0;
ИндексСдвига = ИндексСдвига - 1;
КонецЕсли;
КонецЦикла;
// Если индекс сдвига стал меньше 0, значит, мы полностью перебрали все возможные комбинации
Если ИндексСдвига < 0 Тогда
Прервать;
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Преимущества итеративного обхода: Абсолютная безопасность с точки зрения использования памяти платформы «1С:Предприятие». Код работает полностью изолированно в оперативной памяти и не создает временных таблиц в базе данных, что исключает блокировки и накладные расходы на СУБД.
Давайте сопоставим все три подхода, чтобы вы могли уверенно выбрать наиболее подходящий инструмент под конкретные требования вашей системы:
tempdb на SQL-сервере.