Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1716


3.4. разбиения множества

Число разбиений n-элементного множества на k блоков

произвольного размера но таких, что каждый элемент множества оказывается «приписан» к одному из блоков, выражается числом Стирлинга второго рода S(n, k) [6,7]. Очевидно, что

S(n, k) = 0 для k > n. Если согласиться, что существует только один способ разбиения пустого множества на нулевое число непустых частей, то S(0, 0) = 1 (именно такая договоренность, как и в случае с факториалом, приводит в дальнейшем к универсальным формулам). Так как при разбиении непустого множества нужна по крайней мере одна часть, S(n, 0) = 0 при n > 0. Отдельно интересно также рассмотреть случай k = 2. Если непустое множество разделили на две непустые части, то в первой части может оказаться любое подмножество исходного множества, за исключением подмножеств, включающих в себя последний элемент множества, а оставшиеся элементы автоматически попадают во вторую часть. Такие подмножества можно выбрать 2n–1 – 1 способами, что и соответствует S(n, 2) при n > 0.

Для произвольного k можно рассуждать так. Последний элемент либо будет представлять из себя отдельный блок в разбиении и тогда оставшиеся элементы можно разбить уже на

k – 1 частей S(n – 1, k – 1) способами, либо будет перемещен в непустой блок. В последнем случае имеется kS(n – 1, k) возможных вариантов, поскольку последний элемент мы можем добавлять в каждый блок разбиения первых n – 1 элементов на k частей. Таким образом:

      S(n, k) = S(n – 1, k – 1) + kS(n – 1, k),     n > 0.   (5)

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

             (6)

Если же значение k теперь не фиксировать и рассмотреть все разбиения n-элементного множества, то их количество выражается числом Белла.

По формулам (7) можно подсчитать, что в рамках принятых выше допущений можно построить все разбиения множества, состоящего не более чем из 15 элементов (B15=1382958545).

         (7)

Рассмотрим теперь способ генерации всех разбиений исходного множества. Прежде всего следует договориться о том, как обозначать текущее разбиение. Так как в каждом из разбиений участвуют все элементы исходного множества, будем в массиве индексов p записывать в индекс блок, в который попадает каждый из элементов в текущем разбиении. Параметр i в рекурсивной процедуре part означает, что на текущем шаге именно i-й элемент будет размещаться в каждом из допустимых для него блоков, а j как раз и определяет максимальный номер допустимого блока. После того, как i-й элемент помещен в один из блоков, рекурсивно решается такая же задача для следующего элемента (в данном случае фактически работает универсальная схема перебора с возвратом см. гл. 2).

 

Partition(n, p);

 

  Part(i, j: integer);

 {

   1 if( i > n) Печать(n, p)

   2 else

   3  For (l¬1; l £ j; l¬l+1)

    4 {

    5     p[i] ¬ l;

     6    if( l = j ) part(i+1, j+1)

     7             else part(i+1, j)

     8 }

     9 } /* Конец процедуры part*/

 

{ /* Начало процедуры partition */

  1   part(1,1)

}/*Конец процедуры partition*/

 

В данном случае процедура print оказывается совсем не тривиальной, если требуется печатать (или анализировать) элементы каждого из блоков разбиения в отдельности. Поэтому приведем возможный вариант ее реализации (как и ранее, мы распределяли по блокам индексы, а печатаем или анализируем сами элементы исходного массива a):

 

 Print(n; p);

 {

  1   imax¬1;/*определяем количество блоков в разбиении*/

  2   For (i¬2; i £ N; i¬i+1)

  3  if (p[i]>imax ) imax¬p[i];

  4  For (i¬1; i £ imax; i¬i+1) /*цикл по блокам */

   5{

   6  For (j¬1; j £ N; j¬j+1)  

   7     if (p[j]=I) Печать (a[j]); /*блок напечатан */

    }

  /* разбиение напечатано */

}

 

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

Если при этом рассматривать массив p как n-значное число n-ричной системы счисления, то можно ввести понятие лексикографического порядка для разбиений множества и ставить задачу определения номера разбиения и обратную ей. Как и ранее (см. п. 3.1.3.), они решаются методом динамического программирования и не используют непосредственную генерацию всех разбиений.