Некоторые способы разбиения множеств (стр. 1 из 3)
Введение
В наш бурно развивающийся век, казалось бы, все алгоритмы, которые можно придумать, уже придуманы. Но иногда встречаются задачи, для которых нет подходящих алгоритмов. Быть может потому, что задача редко встречается или, скорее всего для этой задачи нет эффективных алгоритмов (а, скорее всего, их и вовсе не существует).
В этой работе будет обсуждаться тема разбиений множеств.
В [1] автор даёт несколько таких алгоритмов: генерирование всех подмножеств n-элементного множества, генерирование всех k-элементных подмножеств множества {1, …, n} в лексикографическом порядке, генерирование всех разбиений множества {1, …, n} (на этом алгоритме остановимся подробней), нахождение всех разбиений числа.
Первый из этих алгоритмов использует идею бинарного кода Грэя, остальные основаны на удалении или добавлении одного элемента. Последний алгоритм использует схему разбиения большего числа на меньшие числа.
Постановка задачи
Формулировка первой задачи, которую мы рассмотрим, выглядит так: необходимо сгенерировать все разбиения множества, содержащего n элементов.
Для формулировки второй задачи необходимо ввести некоторые понятия.
Итак, дано множество, состоящее из n элементов. Каждый элемент этого множества образует некоторое понятие. Два или больше понятия могут быть объединены в новое понятие. Отличительная черта понятий – взятие их в круглые скобки.
Задача выглядит так: сгенерировать все понятия, которые могут быть образованы из n элементов. Например, для n=3 имеем такие понятия (круглые скобки в начале и в конце опущены для краткости): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математическое обоснование
Под разбиением n-элементного множества Х на k блоков будем понимать произвольное семейство
, такое, что 
для 1£і<j£k и 
для 1£i£k. Подмножества 
будем называть блоками семейства π. Множество всех разбиений множества Х на k блоков будем обозначать 
, а множество всех разбиений через П(Х). Очевидно, что 
(более того, 
является разбиением множества П(Х)).Число Стирлинга второго рода S(n,k) определяется как число разбиений n-элементного множества на k блоков:
где |X|=n.Очевидно, что S(n,k)=0 для k>n. Принимают также S(0,0)=1, так как пустое семейство блоков является в соответствии с определением разбиением пустого множества. С числами Стирлинга второго порядка связано много любопытных тождеств:
S(n,k)=S(n-1,k-1)+kS(n-1,k) для 0<k<n, (1)
S(n,n)=1 для n≥0, (2)
S(n,0)=0 для n>0. (3)
Формулы (2) и (3) очевидны. Для доказательства формулы (1) рассмотрим множество всех разбиений множества {1, …, n} на k блоков. Это множество распадается на два различных класса: тех разбиений, которые содержат одноэлементный блок {n}, и тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока. Мощность первого класса равна S(n-1,k-1), т. е. такова, каково число разбиений множества {1, …, n-1} на (k-1) блоков. Мощность другого класса составляет kS(n-1,k), так как каждому разбиению множества {1, …, n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочерёдно к каждому блоку.
Формулы (1)-(3) позволяют легко вычислять значения S(n,k) даже для больших значений n и k.
Вот другая рекуррентная зависимость:
для k≥2. (4)Для доказательства тождества рассмотрим множество всех разбиений S(n,k) множества Х={1, …, n}. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что для каждого b-элементного подмножества
содержащего элемент n, существует в точности S(n-b,k-1) разбиений множества Х на k блоков, содержащих В в качестве блока. Действительно, каждое такое разбиение однозначно соответствует разбиению множества Х\В на k-1 блоков. b-элементное множество содержащее элемент n, можно выбрать 
способами; таким образом, 
Число Белла
определяется как число всех разбиений n-элементного множества 
где |X|=n.Другими словами,
Докажем рекуррентную зависимость, связанную с числами Белла:
(5)(принимаем
). Доказательство проводится аналогично доказательства тождества (4). Множество всех разбиений множества Х={1, …, n+1} можно разбить на различные классы в зависимости от блока В, содержащего элемент n+1, или – что равнозначно – в зависимости от множества Х\В. Для каждого множества 
существует в точности 
разбиений множества Х, содержащих В в качестве блока. Группируя наши классы в зависимости от мощности множества Х\В, получаем формулу (5).Теперь опишем алгоритм генерирования всех разбиений множества.
Отметим, что каждое разбиение p множества {1,…, n} однозначно определяет разбиение
множества {1,…,n-1}, возникшее из p после удаления элемента n из соответствующего блока (и удалению образовавшегося простого блока, если элемент n образовывал одноэлементный блок). Напротив, если дано разбиение 
множества {1, …, n-1}, легко найти все разбиения π множества {1, …, n}, такие что 
, т. е. следующие разбиения: 
Если нам дан список
всех разбиений множества {1, …, n-1}, то список 
всех разбиений множества {1, …,n}, будем создавать, заменяя каждое разбиение σ в списке на соответствующую ему последовательность (6). Если обратить порядок последовательности (6) для каждого второго разбиения , то элемент n будет двигаться попеременно вперёд и назад, и разбиения «на стыке» последовательностей, образованных из соседних разбиений списка мало отличаются один от другого.Разбиение множества {1, …, n} мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Этот наименьший элемент блока мы будем называть номером блока. Отметим, что номера соседних блоков, вообще говоря, не являются соседними натуральными числами. В этом алгоритме мы будем использовать переменные pred[і], sled[і], 1≤і≤n, содержащие соответственно номер предыдущего и номер следующего блока с номером і (sled[і]=0, если блок с номером і является последним блоком разбиения). Для каждого элемента і, 1≤і≤n, номер блока, содержащего элемент і, будет храниться в переменной blok[і], направление, в котором «движется» элемент і, будет закодировано в булевской переменной wper[і] (wper[і]=true, если і движется вперёд).
Можно показать, что среднее число шагов, необходимых для построения каждого следующего разбиения, ограничено постоянной, не зависящей от n(конечно, если не учитывать число шагов, необходимых для написания разбиения).
| ( 1 2 3 4 ) ( 1 2 3 )( 4 ) ( 1 2 )( 3 )( 4 ) ( 1 2 )( 3 4 ) ( 1 2 4 )( 3 ) ( 1 4 )( 2 )( 3 ) ( 1 )( 2 4 )( 3 ) ( 1 )( 2 )( 3 4 ) ( 1 )( 2 )( 3 )( 4 ) ( 1 )( 2 3 )( 4 ) ( 1 )( 2 3 4 ) ( 1 4 )( 2 3 ) ( 1 3 4)( 2 ) ( 1 3 )( 2 4 ) ( 1 3)( 2 )( 4 ) |
Табл.1. Последовательность разбиений множества {1,2,3,4}
Опишем теперь алгоритм решения задачи о перечислении всех понятий.
Рекурсивный алгоритм использовать нельзя, так как все решения подзадачи меньшей размерности необходимо скомбинировать со всеми решениями подзадачи оставшейся размерности. Поэтому, будем просто перебирать все варианты.
Идея такова: сохраняем все разбиения меньшей размерности и комбинируем их так, чтобы