Малистов А.С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек»
ГЕНЕРАЦИЯ ВСЕХ ОГРАНИЧЕННЫХ РАЗБИЕНИЙ МНОЖЕСТВА
Ограниченное разбиение множества - это способ представить это множество в виде объединения непересекающихся непустых подмножеств ограниченной мощности. Мы представляем алгоритм генерации всех ограниченных разбиений множества.
Ключевые слова: ограниченные разбиения, непересекающиеся подмножества, алгоритм генерации, комбинаторика.
GENERATING ALL RESTRICTED SET PARTITIONS
Restricted partitions of a set are the ways to regard that set as a union of nonempty, disjoint subset with restricted cardinality. We present an algorithm for generating all restricted set partitions.
Keywords: restricted partitions, disjoint subset, restricted cardinality, algorithm.
Разбиение множества из семи элементов на подмножества можно сделать
877-ю способами, однако среди этих способов существуют и те, что включают пятиэлемент-ные подмножества, шестиэлементные подмножества и даже все множество. Чтобы сгенерировать все эти разбиения, можно воспользоваться алгоритмом, который был предложен Джорджем Хатчинсоном в 1963 году. Описание его метода можно найти в [1]. Количество всех возможных разбиений данного множества мощности п на непересекающиеся подмножества равно числу Белла К сожалению, последовательность [£»,,} достаточно быстро возрастает. Можно показать, что Ви = / hi£tt}n [1]. Из-за такого быстрого роста разумный перебор возможен только при малых п.
Иногда достаточно рассматривать лишь ограниченные разбиения, подмножества которых содержат не более, чем г элементов. Пусть ~~ число способов разбить множество (1Д,...if]- на подмножества, мощность каждого из которых не превышает г. Число разбиений задаётся рекуррентной суммой
поскольку каждое разбиение множества [1, 1} получается для некоторого к путём
присоединения к последнему элементу ещё к элементов (Л < г,к <, и,), которые можно выбрать способами, и разбиения оставшихся п — к элементов на ограниченные части способами. Так, например, число разбиений множества из 9 элементов на подмножества размером не более 2, равно = 2620, что более чем в 8 раз меньше количества разбиений на неограниченные по размеру подмножества = 21147).
Разработаем алгоритм, который генерирует все ограниченные разбиения, но при этом проходит по меньшей коллекции различных комбинаций. Для этого модифицируем схему генерации, предложенную Джорджем Хатчинсоном. Его метод использует одно из наиболее удачных представлений разбиения множества ...,-«3 в компьютере, которое кодирует разбиение ограниченно растущей строкой, т. е. строкой <г1 в, .,„a„, в которой
£ж = ff И ^ 1 + ПиЦв^-г^ для 1 j < тт. (1)
При этом ftj = a-ц тогда и только тогда, когда элементы i и k принадлежат одному и тому же блоку.
Чтобы просматривать только ограниченные разбиения, будем в процессе выполнения алгоритма рассчитывать число элементов в каждом блоке. Это позволит предотвратить посещение недопустимых ограниченно растущих строк. Допустимой строкой мы будем называть строку, соответствующую разбиению, в котором мощность каждого блока не превосходит заданного г.
У к с,
-У <
(2)
где 5ц - символ Кронекера:
а
Алгоритм Нг (Допустимые ограниченно растущие строки в лексикографическом порядке). Для данных м £ 2 и г ^ 2 этот алгоритм генерирует все ограниченные разбиения {1А в которых мощность каждого блока не превышает г, путём посещения всех
ограниченно растущих строк сл удовлетворяющих условиям (1) и (2). Как и в ориги-
нальном алгоритме Хатчинсона, поддерживается вспомогательный массив где
Щ= 1+ тох^а^а^); значение переменной ¿?н из соображений эффективности содержится в отдельной переменной т. Кроме того, мы вводим дополнительный массив где
Л- , чтобы следить за числом элементов в блоках. Всякий раз, когда будет меняться значение мы будем производить две операции: сС1 — 1 до изменения и
после.
Нг 1. [Инициализация.] Для всех 1,и установить значения Яу е- [—^—и, ^ "+ 1,
_ №
яв Для всех й = установить = ^^ Значение можно вычислить в про-
.
цессе установки я,-, предварительно установив .
Нг2. [Посещение.] Если ^ то посетить ограниченно растущую строку которая представляет ограниченное разбиение нат4 = м] блоков. Затем, если = «, перейти к шагу Нг4.
Нг3. [Увеличение а„.] Уменьшить — 1. Установить 4 1, увеличить
+ 1и вернуться к шагу Нг2.
НТ4. [Поиск /.] Установить / « * 1; затем, пока ™ устанавливать / 1 / 1.
Нг5. [Увеличение Я-,-.] Завершить работу алгоритма, если / = 1. В противном случае уменьшить ев, — 1, установить щ а,- + 1, продолжать выполнять щ щ + 1 до тех
пор, пока не окажется св, < г. Наконец, увеличить {- с^ 4 1.
НТ6. [Обновление т.] Установить 1*1- Ь, + [ё^ = Ь^', /*-/ + 1и(«-в
Нт1. [Инициализация я^—в^.] Если / < проверить условие г,Г=г и увеличивать 4 11 4 I 1 до тех пор, пока не станет < г. Потом установить ¿ц, с еа, 1, с с са, 4 1 и = г?ш С/га, 1 ■+ 1). Повторять этот шаг, пока выполняется / < эт..
Нг8. [Возврат.] Увеличивать £Ь 4 1 до тех пор, пока не станет < г. Установить сь = I я<-4 1) и вернуться к шагу
Шаг Й,Д выполняется единожды, а шаги выполняются меньшее число раз,
чем Циклы в шагах и й^?, как и в оригинальном алгоритме Хатчинсона, почти
всегда короткие (см. [1]). Таким образом, время работы всех шагов есть
Когда алгоритм возвращается к выполнению шага й,,2, может произойти одно из двух событий. Либо выполнение шага было эффективным, когда мы посещаем допустимую строку либо оказалось холостым, когда се > г. Число эффективных посещений, очевидно, равно Количество холостых выполнений можно оценить, если считать, что сначала мы выбираем способами г элементов из множества .,,,1? — которые должны
быть присоединены к последнему элементу п, а затем разбить оставшееся множество из к — г — 1 элементов на ограниченные части способами. Итого, время работы алго-
ритма не превышает
о^+с;1)^}
Таким образом, в случае, когда нам требуются лишь ограниченные разбиения мы можем их генерировать, не посещая все возможные способы разбиения, которые требуются в задаче, а лишь те разбиения, в которых размер блока ограничен.
ЛИТЕРАТУРА
1. Кнут Д. Э. Искусство программирования, том 4, выпуск 3: генерация всех сочетаний и разбиений: Пер. с англ. - М.: Издательский дом «Вильямс», 2007.
2. Стенли, Ричард. Перечислительная комбинаторика. - М.: Мир, 1990.
3. Эндрюс Г. Теория разбиений. Перев. с англ. -М.: Наука. Главная редакция физико-математической литературы, 1982.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.