Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПМ

Реферат

Генерация комбинаторных объектов

Исполнитель:

Студентка группы М-43

Самусенко А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент

Лебедева М.Т.

Гомель 2007

Содержание

Введение........................................................................................................... 3

1 Множество всех подмножеств...................................................................... 4

2 Перестановки................................................................................................. 7

3 Сочетания.................................................................................................... 11

4 Размещения.................................................................................................. 14

5 Перестановки с повторениями.................................................................... 17

6 Сочетания с повторениями......................................................................... 20

Заключение..................................................................................................... 23

Литература...................................................................................................... 24

Введение

Существует набор задач, решение которых заключается в генерации всех элементов таких комбинаторных объектов как множество всех подмножеств, перестановки, сочетания, размещения, перестановки с повторениями, сочетания с повторениями.

Для каждого сгенерированного элемента затем проверяются какие-то свойства для конкретной задачи.

В дальнейшем в данной работе предлагается следующий порядок изложения материала для каждого комбинаторного объекта: пример, алгоритм, программа, комментарии к программе.

1 Множество всех подмножеств

Пусть мы имеем множество из 4-х компонент - которые мы обозначаем латинскими буквами A, B, C, D соответственно.

И пусть по условиям задачи требуется выбрать подмножество, состоящее из нескольких компонент, обладающее некоторым свойством. Предлагается такой способ решения задачи: мы генерируем ВСЕ возможные подмножества данного множества и для каждого из сгенерированных подмножеств проверяем удовлетворяет ли оно заданному свойству. Альтернативный вариант задачи - подсчитать ВСЕ подмножества данного множества, обладающие заданным свойством.

Например:

Для множества из 4-х символов A,B,C,D множество всех подмножеств включает в себя следующие множества:

Пустое множество

Одноэлементные множества: {A}, {B}, {C}, {D}

Двухэлементные множества: {A,B}, {A,C}, {A,D} {B,C}, {B,D}, {C,D}

Трехэлементные множества: {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}

Четырехэлементное множество: {A,B,C,D}

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

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

Рассмотрим теперь последовательность двоичных чисел от 0 до 15 и соответствующие им подмножества:

4321

DCBA

0000 - Пустое множество

0001 A

0010 B

0011 AB

0100 C

0101 AC

0110 BC

0111 ABC

1000 D

1001 AD

1010 BD

1011 ABD

1100 CD

1101 ACD

1110 BCD

1111 ABCD

Таким образом, всего имеется 16 различных подмножеств множества из 4-х элементов. В общем случае множество всех подмножеств множества из N элементов содержит 2N (два в степени N) элементов.

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

Формируем массив, состоящий из N нулей - и рассматриваем его как пустое множество. Таким образом, начальное значение текущего подмножества - пустое множество.

Для получения следующего подмножества из текущего подмножества обрабатываем текущий массив из чисел 0 или 1 следующим образом:

Справа (от первого элемента массива к последнему) ищем первое число, равное нулю.

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

Если же элемент равный 0 найден, то он заменяется на 1, а все числа справа от него (если таковые имеются) заменяются на нули.

Более формализовано этот алгоритм может быть записан следующим образом:

Ввод (N)

Обнуление массива B из N+1 элемента