Комбінаторний Аналіз. Методичка

Комбінаторний аналіз. : Методичні вказівки до виконання практичних занять з дисципліни „Комп’ютерна дискретна математика” для студентів спеціальності „Програмне забезпечення автоматизованих систем” / Укл.: П. В. Сердюк, Нитребич О. О. – Львів: Видавництво Національного університету „Львівська політехніка”, 2012. – 40 с.

Укладачі П. В. Сердюк., к. т. н., ст. викл. кафедри ПЗ, О.О. Нитребич, асп. кафедри ПЗ

Відповідальний за випуск Федасюк Д.В., д-р тех. наук, проф.,

Рецензенти Тушницький Р.Б., канд. тех. наук, ст. викл. кафедри ПЗ Денисюк П. Ю. канд. тех. наук, доцент кафедри САПР

КОМБІНАТОРНИЙ АНАЛІЗ

Мета роботи: Ознайомлення на практиці із основними типами та властивостями вибірок, комбінаторними задачами і алгоритмами.

1.Вступ

Укомбінаторному аналізі (комбінаториці) вивчають способи вибору та розміщення об'єктів зі скінченної множини відповідно до заданих правил. У програмній інженерії комбінаторика є основним інструментом для оцінки складності алгоритмів, дослідження операцій, побудови складних ітераційних алгоритмів, дискретної оптимізації, кодування, шифрування та низки інших задач.

2.Основні правила комбінаторного аналізу. Поняття вибірки

Всі обчислення у комбінаториці можна зробити за допомогою двох основних правил: правила суми та правила добутку.

Правило суми. Якщо об'єкт х можна вибрати n способами, а об'єкт y

— m способами, то можна вибрати або х, або у п +m способами.

Приклад 2.1. Один фрукт можна вибрати з одинадцяти мандаринів, дев’яти апельсинів та чотирьох ківі. За правилом суми фрукт можна вибрати 11 + 9 + 4 способами. ▲

Правило добутку. Якщо об'єкт х можна вибрати n способами, а об'єкт y — m способами, і вибір об'єкту х не впливає на кількість способів вибору об'єкту у, то пару об'єктів (х, у ) можна вибрати nm способами.

Приклад 2.2. Потрібно вибрати одну білу та одну чорну фігуру. Дано 10 білих і 16 чорних фігур. Отже, білу та чорну фігуру можна вибрати способами. ▲

Означення 2.1. Вибіркою із множини А = {а1, а2,… аn} називають сукупність об’єктів [b1, b2,… bk], де bi A ,i=1,…,k. У зв’язку з тим, що у

комбінаториці вивчають кількість вибірок, то від значень елементів множини A часто абстрагуються, і говорять про вибірку із n елементів по к, або к-вибірку із n елементів.

Означення 2.2. Вибірка називаються вибіркою без повторень, якщо спосіб вибору її елементів виключає можливості повторів у її елементах, у протилежному випадку її називають вибіркою з повтореннями.

Тип вибірки визначається способом вибору її елементів. Тобто, якщо ми формуємо вибірку без повторень, то при виборі кожного нового елементу його обирають так, щоб він не співпадав з уже вибраними.

Якщо ж ми вибираємо вибірку з повтореннями, то один і той самий елемент із множини А може зустрітись у вибірці декілька разів. Тим не менше, у отриманій вибірці може і не бути повторів елементів, але вона буде вибіркою з повтореннями, бо отримана відповідним способом.

Означення 2.3. Вибірку називають упорядкованою, якщо задано порядок її елементів, а ні — то невпорядкованою. Зрозуміло, що впорядкована r-вибірка — це кортеж (вектор) з k компонентами, і тому її

позначають (b1,b2 ,...,br ,) , bi A , i=1, …, k. Невпорядковану k-вибірку позначатимемо як [b 1 ,b2…,bk] bi A ,i=1,…,k. Упорядковані k-вибірки з n-елементної множини називають розміщеннями з п елементів по k, а невпорядковані — сполученнями з п елементів по k. Використовують також поняття k-розміщення й k-сполучення.

Приклад 2.3. Задано множину А = {1, 2, 3}, тобто n = 3. Наведемо розміщення без повторень із трьох елементів по два, тобто r =2:

(1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2);

розміщення з повтореннями з трьох елементів по два:

(1, 2), (1, 3), (2, 3), (2, 1) (3, 1), (3, 2), (1, 1), (2, 2), (3, 3);

сполучення без повторень із трьох елементів по два:

[1, 2], [1, 3], [2, 3];

сполучення з повтореннями із трьох елементів по два:

[1, 2], [1, 3], [2, 3], [1, 1], [2, 2], [3, 3]. ▲

Зазначимо, що сполучення без повторень з п елементів по r — це просто r-елементні підмножини множини з п елементів; отже, їх можна записати так: {1, 2}, {1, 3}, {2, 3}. Сполучення з повтореннями — це не множина у звичайному розумінні: її елементи можуть повторюватись, тобто зустрічатися більше одного разу.

Означення 2.4. Перестановка з п елементів — це розміщення без повторень з п по п елементів, тобто в розміщення входять усі елементи. Перестановки з п елементів називають також п-перестановками. Кількість перестановок позначають як Рп.

Означення 2.5. Нехай є n елементів k різних типів, а число nj (j=1,…,k) — кількість елементів j-гo типу. Очевидно, що n1+п2+...+nk=п. Перестановки з n елементів за такої умови називають перестановками з повтореннями. Кількість таких перестановок позначають як Рn (п1 п2, ...,

nk).

Приклад 2.4. Знайдемо усі перестановки множини А = {1, 2, 3}. Для цього знайдемо всі можливі комбінації чисел {1, 2, 3}.

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1),(3, 1, 2), (3, 2, 1). ▲

3. Алгоритми перебору та лексикографічний порядок

Алгоритми для перебору дуже великого числа варіантів потрібні для великої кількості прикладних дискретних задач, таких як пошук оптимального рішення, відбір елементів за певними умовами, тощо. Для перебору елементів використовують алгоритми перебору, рекурсії та перебору з поверненням. Найбільш відомі два алгоритми генерації вибірок - рекурсивний і алгоритм лексикографічного порядку перестановок. Стандартна бібліотека шаблонів STL мови програмування С++ містить реалізований алгоритм для знаходження наступної в лексикографічному порядку перестановки next_permutation.

Розглянемо алгоритми перебору, які полягають в генерації всіх можливих варіантів усіх об’єктів, що задовольняють певні умови. У цьому розділі ми розглянемо перебір усіх вибірок із множини А. Для спрощення записів задачі розміщення (а1, а2,..., аr) позначатимемо як a1a2 ...ar , і розглядатимемо розміщення множини А={1, 2,…, п} - індексів об’єктів, так як довільну множину можна проіндексувати шляхом присвоєння кожному об’єкту індивідуального номеру. Для перебору набагато зручніше користуватись індексами, а не реальними об’єктами.

Для реалізації перебору потрібно:

встановити лексикографічний порядок елементів, що підлягають перерахуванню (зокрема, визначити, який з них буде першим, а який останнім);

знайти алгоритм переходу від довільного елементу до лексикографічно наступного (безпосередньо наступного) за ним.

Алгоритм ґрунтується на послідовному переході по елементах у лексикографічному порядку, починаючи від мінімального і завершуючи максимальним.

Означення 3.1. Лексикографічний порядок – це природний спосіб упорядкування послідовностей на основі порівняння індивідуальних символів. На множині всіх розміщень із r елементів означимо порівняння таким чином: b1b2 ...br < a1a2 ...ar , якщо

m : bi ai ,i m bm am .

У такому разі говорять, що перестановка b1b2 ...br менша від перестановки a1a2 ...ar , або перестановка a1a2 ...ar більша від перестановки

b1b2 ...br .

У програмуванні такий лексикографічний порядок використовують для

порівняння стрічок, тільки замість чисел беруть символи ASCII чи Unicode (в залежності від типу стрічки) і лексикографічний порядок відповідає порядку символів.

Приклад 3.1. Порівняємо стрічки hello та hermes. Очевидно, що перша та друга літера однакові. Тому порівняння визначатиме третя літера. У таблиці ASCII (чи відповідно до англійської абетки) літера l передує літері m. Тому hello < hermes.▲

Означення 3.2. Вибірку a1a2 ...ar називають лексикографічно наступною (безпосередньо наступною) за b1b2 ...br , якщо не існує такої вибірки c1c2 ...cr , що:

b1b2 ...br < c1c2 ...cr < a1a2 ...ar .

Визначимо, яким чином можна побудувати лексикографічно наступне розміщення за розміщенням a1a2 ...ar .

4. Алгоритми перебору розміщень

Алгоритм побудови лексикографічно наступного розміщення з повтореннями за розміщенням а1а2...аr

Алгоритм подібний до звичайного визначення наступного числа.

Крок 1. Знаходимо позицію k першого справа числа, відмінного від n ak n .

Крок 2. Збільшуємо елемент ak на одиницю. Елементи ai , де i<k залишаються без змін. Елементи ai , де i>k стають рівними одиниці.

Приклад 4.1. Нехай A = {1, 2 ,3}. Побудуємо 6 розміщень з повтореннями лексикографічно наступних після 1222. Наступне буде 1223, так як можливо збільшити останній елемент. Після нього буде 1231 - оскільки 4-й елемент ми збільшити не можемо, то збільшуємо 3-й, а 4-й ставимо рівним одиниці. Як бачимо, маємо аналогію з переносом розряду, подібно до десяткового числення. Наступні елементи, відповідно будуть 1232,1233, 1311 та 1312.▲

Алгоритм побудови лексикографічно наступного розміщення без повторень за розміщенням а1а2...аr

Алгоритм від попереднього відрізняється тим, що у розміщеннях не може бути повторів, і тому потрібно “оновлювати” елементи розміщення, не порушуючи цієї властивості.

Крок 1. Знайдемо множину B “вільних” чисел, яких немає у розміщенні a1a2 ...ar : B = A\ a1a2 ...ar .

Наведемо кроки алгоритму.

Крок 1. Знайти такі числа aj і aj+i, що (аj<аj+1, ) (aj+i aj+2 ... ап). Для цього треба знайти в перестановці першу справа пару сусідніх

чисел, у якій число ліворуч менше від числа праворуч.

Крок 2. Записати в j-ту позицію таке найменше з чисел aj+1, aj+2,..., ап, яке водночас більше, ніж aj.

Крок 3. Записати у висхідному порядку число аj і решту чисел aj+1,

aj+2,...,an у позиції j + 1,..., п.

Приклад 5.1. Побудуємо 2 перестановки, наступні в лексикографічному порядку за 34521. Згідно першого кроку j=2, бо 4<5>2>1. Отже, перше число (3) залишається на місці, а збільшується друге число(4). Розглянемо послідовність чисел 521. Серед них найменше число, більше від 4, це 5. Тепер на другому місці 5, а решту чисел розміщуємо у вихідному порядку: 35124.

Побудуємо наступну перестановку після 35124. Згідно першого кроку j =4, і щоби отримати наступну перестановку, треба збільшити “2”, поставивши замість нього “4”, так як справа немає іншого числа більше “2”. Переставивши місцями два останніх числа, ми отримаємо 35142.▲

Іншим алгоритмом для перебору всіх розміщень є генерування усіх сполучень (див. наступний розділ), після чого з кожного сполучення генерувати всі можливі перестановки.

Зауважимо також, що для перебору перестановок з повтореннями чи без повторень алгоритм не відрізнятиметься. Єдина відмінність полягатиме у тому, що для перестановок без повторень рівності у кроці 1 будуть строгими.

Приклад 5.2. Побудуємо 5 перестановок, наступних в лексикографічному порядку за 324122311. Знаходимо перші 2 числа справа, перше х яких менше другого: 2 3 1 1. Отже, на місце першого числа ставимо “3”, а решту ставимо в порядку зростання (112), отримуємо 3241243112. Наступне число отримується перестановкою двох останніх чисел 3241243121. Легко побачити, що наступне 3241243211.

Щоб знайти наступне після 3241243211, знову знаходимо перші 2 числа справа, перше х яких менше другого: 2 4 3 2 1 1.

Збільшуємо “2” на наступне число, наявне справа від нього у перестановці - “3”. Решту чисел сортуємо по зростанню: 3241311224. ▲

6. Алгоритми перебору сполучень

Як і в попередньому розділі, розглядатимемо перебір сполучень на

множині A={1,2,…,n}. Сполучення без повторень з n елементів по r — це r-елементна підмножина множини А. Позаяк порядок запису елементів множини неістотний, то для спрощення запису будемо сортувати елементи в сполученнях у висхідному порядку, і записувати їх як рядок чисел: наприклад, сполучення {4,1,3} будемо записуватимемо як 134.

Алгоритм побудови лексикографічно наступного сполучення з повтореннями за сполученням а1,а2...аr

Алгоритм подібний до алгоритмів генерування розміщень, але має одну особливість, яка полягає в наступному: якщо сполучення впорядковане у висхідному порядку, то кожен наступний елемент сполучення не менший за попередній.

Крок 1. Знаходимо позицію k першого справа числа, відмінного від n: ak n .

Крок 2. Збільшуємо елемент ak на одиницю bk ak 1. Елементи зліва ai залишаються без змін bi ai ,де i<k .

Елементи справа ai , де i>k стають рівними bk , bi bk ,де i k .

Приклад 6.1. Нехай A = {1, 2 , 3, 4}. Побудуємо 7 сполучень з повтореннями лексикографічно наступних після 1233. Наступне буде 1234, так як можливо збільшити останній елемент.

При пошуку наступного сполучення після 1234 бачимо, що збільшувати можна “3”. Отже отримаємо 124. Останній елемент теж повинен бути рівний “4”, бо не може бути менший за попередній. Отже отримуємо 1244.

Після нього буде 1333 - оскільки ми можемо збільшити тільки “2”, а інші елементи мають бути такими самими. Аналогічно знаходимо наступні елементи:

1334, 1344, 1444 та 2222.▲

Алгоритм побудови лексикографічно наступного сполучення без повторень за сполученням а1а2...аr

Перед тим як розглянути алгоритм, розглянемо одну особливість. Якщо сполучення впорядковане у висхідному порядку і не має повторів, то кожен наступний елемент сполучення більший від попереднього принаймі на одиницю.

Тоді максимальне значення, яке може набувати його останній елемент, рівне n. Максимум для передостаннього елементу рівний n-1, а не n. Доведемо це від зворотнього. Припустимо. що останній елемент рівний n , тоді наступний елемент має бути рівний n +1, але такого елементу немає в множині. Отже максимум передостаннього елементу n-1. Аналогічно можна довести, що максимум елементу на k-ій позиції рівний n-( r-k). Мінімум елементу – попереднє число сполучення, збільшене на одиницю.

Крок 1. Знайдемо перший справа елемент сполучення, який можна збільшувати. Він