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

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

Студентка группы М-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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--