Міністерство освіти Республіки Білорусь
Установа навчання
В«Гомельський державний університет ім. Ф. Скорини В»
Математичний факультет
Кафедра МПМ
Реферат
Генерація комбінаторних об'єктів
Виконавець:
Студентка групи М-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 елемента
Висновок (Пусте безліч)
Поки B [N +1] = 0
i = 1
Поки B [i] = 1 робити B [i] = 0, i = i +1
B [i] = 1
Висновок (безлічі, що визначається масивом B)
Нижче наводиться текст програми, яка зчитує N - число елементів у множині і виводить на екран безліч всіх підмножин позначаючи елементи відповідними по порядку латинськими літерами:
const
<...
