В практике программирования на платформе 1С:Предприятие часто возникают задачи, связанные с комбинаторикой: распределение заказов по транспортным средствам, группировка платежей по счетам или формирование партий товаров. Одной из наиболее сложных задач в этой области является поиск всех возможных вариантов распределения элементов по группам (массивам), при условии, что порядок элементов внутри группы и порядок самих групп не имеет значения. В математике эта задача называется нахождением всех разбиений множества.
Разберем детально, как подойти к решению этой задачи, какие алгоритмы использовать и с какими ограничениями платформы придется столкнуться.
Прежде чем приступать к написанию кода, проанализируем условия. Допустим, у нас есть три элемента: 0, 1, 2. Нам нужно найти все уникальные способы их распределения. Согласно правилам комбинаторики, для трех элементов существует ровно 5 вариантов:
(0, 1, 2)(0, 1) и (2)(0, 2) и (1)(1, 2) и (0)(0), (1), (2)Важно понимать, что вариант (0) и (2, 1) — это то же самое, что (1, 2) и (0), так как порядок элементов и массивов не важен. Количество таких способов разбиения для $n$ элементов называется числом Белла. Выясним причину, по которой это важно: числа Белла растут чрезвычайно быстро. Для 10 элементов это уже 115 975 вариантов, а для 20 элементов — более 51 триллиона. Поэтому, если ваша задача подразумевает обработку 100 элементов (как упоминалось в обсуждении), важно сразу осознать: вычислить и сохранить все варианты физически невозможно ни на одной современной системе.
Рассмотрим наиболее эффективный алгоритм генерации таких распределений — использование последовательностей ограниченного роста. Этот метод позволяет генерировать только уникальные варианты, автоматически исключая дубликаты и перестановки.
Суть метода заключается в создании массива индексов, где каждое число обозначает номер «корзины» (массива), в которую попадает элемент. Чтобы избежать дублей, накладывается правило: первый элемент всегда попадает в корзину 0, а каждый следующий может либо попасть в уже созданную корзину, либо в новую, индекс которой на единицу больше максимального из существующих.
Проанализируем пример для 3 элементов:
[0, 0, 0] — все элементы в группе 0.[0, 0, 1] — первые два в группе 0, третий в группе 1.[0, 1, 0] — первый и третий в группе 0, второй в группе 1.[0, 1, 1] — первый в группе 0, второй и третий в группе 1.[0, 1, 2] — каждый элемент в своей группе.Посмотрим на пример реализации алгоритма с использованием рекурсии. Мы будем передавать текущий индекс обрабатываемого элемента и массив уже распределенных индексов групп.
Процедура РаспределитьЭлементы(ТекущийИндекс, КоличествоЭлементов, ТекущаяСхема, МаксГруппа, Результат)
// Если распределили все элементы, фиксируем результат
Если ТекущийИндекс = КоличествоЭлементов Тогда
Результат.Добавить(СформироватьВариант(ТекущаяСхема));
Возврат;
КонецЕсли;
// Пробуем добавить текущий элемент в каждую из существующих групп
Для НомерГруппы = 0 По МаксГруппа Цикл
ТекущаяСхема[ТекущийИндекс] = НомерГруппы;
РаспределитьЭлементы(ТекущийИндекс + 1, КоличествоЭлементов, ТекущаяСхема, МаксГруппа, Результат);
КонецЦикла;
// И пробуем создать новую группу
ТекущаяСхема[ТекущийИндекс] = МаксГруппа + 1;
РаспределитьЭлементы(ТекущийИндекс + 1, КоличествоЭлементов, ТекущаяСхема, МаксГруппа + 1, Результат);
КонецПроцедуры
В данном коде ТекущаяСхема — это массив целых чисел, а Результат — общий список всех найденных вариантов. Метод СформироватьВариант должен преобразовать схему индексов в структуру Массив, содержащий Массивы элементов, как того требует задача.
Проанализируем ситуацию с памятью. Объект Массив в 1С является достаточно «тяжелым». Если мы будем хранить миллионы вариантов в структуре «Массив массивов массивов», оперативная память сервера (rphost) закончится мгновенно. Рассмотрим шаги по оптимизации:
МассивРезультат, обрабатывайте каждый вариант сразу после его генерации (внутри рекурсии).Как справедливо отмечено в обсуждении, «голая» комбинаторика редко нужна в чистом виде. Выясним, как упростить задачу. В реальных задачах всегда есть ограничения:
Внедрение этих проверок непосредственно в процесс рекурсии (отсечение ветвей дерева) позволяет сократить количество вариантов на несколько порядков, делая задачу решаемой даже для 25–30 элементов.
Подводя итог, можно сказать, что алгоритм распределения элементов — это мощный инструмент, который требует от программиста 1С не только знания синтаксиса, но и понимания вычислительной сложности. Использование метода строк ограниченного роста является «золотым стандартом» для решения этой задачи без дубликатов.