Построение всех разбиений множества на подмножества

Количество перестановок на местах

Есть мест и нам важно на каких места будут стоять элементы каждого типа. Разобьём мест на группы, 1-ая – места для первого типа, 2-ая – места для второго типа, …. В результате количество перестановок равно количеству разбиений.

Иногда требуется разбить множество на подмножества различными способами.

Для построения всех разбиений можно использовать следующий алгоритм:

Выдаем все разбиения для множества из 1-ого элемента (1-ый). Затем по нему строятся разбиения для множества из 2-ух элементов (1-ый и 2-ой), по ним строятся все разбиения множества из 3-х элементов (1-ый, 2-ой, 3-ий) и т.д. Получим все разбиения из элементов.

Множество из 1-ого элемента разбивается единственным способом: . Добавим нулевое множество: . Затем второй элемент добавим в каждое из подмножеств входящих в разбиения: . Затем в каждое разбиение добавим : . Затем в каждое разбиение добавим 3-ий элемент: , добавим и т.д.

Дата добавления: 2014-01-07; Просмотров: 870; Нарушение авторских прав?; Мы поможем в написании вашей работы!