Некоторые способы разбиения множеств

Введение

В наш бурно развивающийся век, казалось бы, все алгоритмы, которые можно придумать, уже придуманы. Но иногда встречаются задачи, для которых нет подходящих алгоритмов. Быть может потому, что задача редко встречается или, скорее всего для этой задачи нет эффективных алгоритмов (а, скорее всего, их и вовсе не существует).

В этой работе будет обсуждаться тема разбиений множеств.

В [1] автор даёт несколько таких алгоритмов: генерирование всех подмножеств n-элементного множества, генерирование всех k-элементных подмножеств множества {1, …, n} в лексикографическом порядке, генерирование всех разбиений множества {1, …, n} (на этом алгоритме остановимся подробней), нахождение всех разбиений числа.

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

Постановка задачи



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

Для формулировки второй задачи необходимо ввести некоторые понятия.

Итак, дано множество, состоящее из n элементов. Каждый элемент этого множества образует некоторое понятие. Два или больше понятия могут быть объединены в новое понятие. Отличительная черта понятий – взятие их в круглые скобки.

Задача выглядит так: сгенерировать все понятия, которые могут быть образованы из n элементов. Например, для n=3 имеем такие понятия (круглые скобки в начале и в конце опущены для краткости): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).