4.7. Порождение композиций и разбиений

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

Разбиение называется композицией числа если учитывается порядок чисел Как правило, представляют интерес композиции, в которых либо все либо все

Разбиение называется разбиением числа если все и порядок чисел не важен. По сути разбиение числа является мультимножеством (см. п. 1.8).

Рассмотрим примеры разбиения числа

— все композиции числа три из двух частей, — все композиции числа три из трех частей, — все композиции числа три из двух частей,

— все разбиения числа три.

Композиции ...

Композицию где числа можно интерпретировать следующим образом. Каждое значение представим как сумму единиц, количество которых Индекс у элемента 1, показывает его принадлежность разложению числа Таким образом, мы ввели к типов различных элементов значение каждого из них равно единице. Теперь любую композицию можно представить как сумму, составленную из произвольных единиц множества Суммируя подобные единицы 1, с одинаковыми индексами, получим соответствующие значения композиции. Данное соответствие является взаимно однозначным, откуда и следует, что число композиций равно числу сочетаний с повторениями Каждое из сочетаний можно интерпретировать как расстановку длины в которой единиц и нуль, т.е. каждому сочетанию ставим в соответствие - -разрядное число из единиц и нулей; верно и обратное. Суммируя в таком числе слева направо единицы между нулями (их ), будем получать соответствующие значения членов (их k) композиции. Например, одному из сочетаний 11011100111101111111010 соответствует композиция (2,3,0,4,7,1,0) числа 17.

Ясно, что методы предыдущего раздела генерации подмножеств множества легко применить к последовательному порождению рассмотренных композиций

Композиции ...

Удобное представление композиций получается из рассмотрения целого числа как отрезка прямой, состоящего из отрезков единичной длины. Линия разделена точками, и композиция

(см. скан)

получается пометкой некоторых из них. Элементами композиции являются просто расстояния между смежными точками. На рисунке показано графическое представление композиции (2,1,2,2,1) для числа Очевидно, что каждая композиция числа соответствует способу выбора подмножества из точек. Каждой точке можно сопоставить двоичную цифру, и, таким образом, композиции будет соответствовать -разрядное число. В этой интерпретации композиция из Участей соответствует -разрядному числу ровно с единицами, и поэтому существует таких композиций.

Воспользуемся методами предыдущего раздела для генерации композиций Учитывая, что в композиции каждый из тогда для новых переменных соответствующая композиция будет для числа Генерация слагаемых композиции подробно разобрана в предыдущем разделе, добавляя к каждому из по единице, получим слагаемые композиции

Разбиения

Разбиения отличаются от композиций тем, что порядок компонент не важен, так что, например, не делается различия между, скажем, Таким образом, разбиение можно рассматривать как мультимножество, которое записывается следующим способом:

где имеется вхождений вхождений вхождений и т. д. и Каждое разбиение удовлетворяет условию

Рассмотрим пример генерации разбиений для Последовательность генерации разбиений данного примера далее будет положена в основу алгоритма порождения полного списка разбиений.

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

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

Алгоритм 4.13 использует рассмотренный процесс для порождения всех разбиений числа

Алгоритм 4.13. Генерация разбиений числа

(см. скан)

Алгоритм 4.13 линеен, так как число операций, необходимых для перехода от одного разбиения к другому, ограничено константой, не зависящей от

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

Алгоритм 4.14. Программа на Pascal'е генерации разбиений числа

(см. скан)

(см. скан)