Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПМ
Реферат
Генерация комбинаторных объектов
Исполнитель:
Студентка группы М-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-х элементов. ............
