Гостьова книга - персональний сайт
Вступ
У даній статті буде розглянуто ряд класичних розділів комбінаторики, таких як, розбиття можество і чисел, розміщення і поєднання, перестановки, біноміальні коефіцієнти і ін.), А також алгоритми генерації комбінаторних об'єктів.
При вивченні різних комбінаторних об'єктів, ми, в першу чергу, будемо відповідати на ряд класичних питань:
1. Скільки елементів містить досліджуване безліч?
2. Яким чином можна перебрати елементи даної множини?
3. Як можна перенумерувати ці елементи? Т. е. Як, знаючи кількість елементів n, сформувати взаимнооднозначное відповідність між елементами і числами 1: n?
Перебір 0-1 векторів
Для зручності, розглянемо в якості досліджуваного комбинаторного об'єкта безліч Bm наборів з m нулів і одиниць. Для цього безлічі дамо відповіді на поставлені питання.
Зрозуміло, що безлічі наборів з m нулів і одиниць містить рівно 2m елементів.
Для того, щоб створити обчислювальний процес, при якому на кожному кроці буде формуватися новий, не зустрічався раніше, елемент розглянутого безлічі, достатньо зауважити, що існує взаимнооднозначное відповідність між числами з 0 ... 2m # 8722; 1 і наборами 0-1 векторів. Т. е. Досить першим взяти число 0 і його двійкове подання 0, ..., 0, а потім просто додавати по одиниці, імітуючи це на поточному наборі, поки ми не дійдемо до набору з одних одиниць.
Крім розглянутого способу перебору наборів, можна запропонувати інший алгоритм, який на кожному кроці змінює значення тільки однієї компоненти. Цей алгоритм заснований на ідеї рекурсії.
1. Фіксуємо нульове значення m-й компоненти і перебираємо всі набори довжини m # 8722; 1 для решти компонент.
2. Міняємо значення m-й компоненти з 0 на 1. Перебираємо набори довжини m # 8722; 1 в зворотному порядку.
Наведемо таблицю, яка показує процес перебору наборів довжини 4. Стовпець it показує номер поточної ітерації, а стовпець kit - номер компоненти, яка підлягає оновленню.
Також легко можна дати відповідь на питання про те, як перенумерувати набори безлічі. Дійсно, поточний набір безлічі - це двійкове подання деякого числа, яке і є номером нашого набору. Таким чином, ми кожного набору можемо зіставити його чисельний еквівалент.
коди Грея
Раніше ми розглядали рекурсивний алгоритм перебору 0-1 наборів. Цей алгоритм дозволяє перебирати всі набори Bm так, щоб кожен наступний набір відрізнявся від попереднього тільки в одному розряді. Побудована за допомогою цього алгоритму послідовність наборів (наводиться в таблиці) називається кодом Грея. Взагалі, n-розрядний код Грея - це впорядкована (можливо, циклічна) послідовність, що складається з 2n n-розрядних кодових слів, кожне з яких відрізняється від сусіднього в одному розряді.
Наведемо ще один (на цей раз нерекуррентний) алгоритм генерації кодів Грея. Будемо розглядати бінарні коди Грея порядку n. Отже, на вхід алгоритму подається однина n, яке вказує порядок коду Грея. По ходу виконання алгоритму ми отримаємо послідовність всіх підмножин n-елементного безлічі, в якій кожне наступне підмножина виходить з попереднього додаванням або видаленням єдиний елемент (найменшим можливим зміною) - код Грея. При цьому кожна підмножина буде представлятися бінарної послідовністю B [1], ..., B [n].
Gray-Generation (n)
1 for i: = 1 to n do B [i]: = 0;
2 i: = 0;
3 repeat
4 write (B [i], ..., B [n]);
5 i: = i + 1; p: = 1; j: = i;
6 while j mod 2 = 0 do
7 begin
8 j: = j / 2; p: = p + 1;
9 end;
10 if p # 8804; n then B [p]: = 1 # 8722; B [p];
11 until p> n
Доведення коректності роботи алгоритму можна знайти в [1].
Послідовність отриманих підмножин можна проілюструвати на графі (n-вимірному кубі), вершини якого відповідають бінарним послідовностям довжини n і дві вершини якого з'єднані ребром, якщо відповідні послідовності відрізняються лише в одній позиції. Тоді ця послідовність відповідає гамільтоновим шляху в цьому графі, т. Е. Шляху, який містить кожну вершину графа тільки один раз.
Перебір елементів прямого твори множин
Якщо ми розглядаємо два будь-яких безлічі A і B, то будемо називати їх прямим (декартових) твором (A # 215; B) множин A і B, безліч всіляких упорядкованих пар (i, j), де i # 8712; A, j # 8712; B. Потужність ж безлічі, отриманого при декартовом творі множин, буде дорівнює добутку потужностей цих множин.
Більш того, ми можемо визначити пряме твір будь-якого кінцевого числа множин. Наприклад, якщо розглядати екземпляри тільки одного безлічі, що складається з двох елементів 0 і 1, то пряме твір m таких екземплярів буде являти собою раніше расcмотренное безліч Bm.
Отже, розглянемо пряме твір k множин: M1 # 215; M2 # 215; ... # 215; Mk. Очевидно, що
| M1 # 215; M2 # 215; ... # 215; Mk | = # 8719; i # 8712; 1: k mi,
де mi = | Mi | - кількість елементів множини Mi.
Нехай безліч Mi складається з цілих чисел від 0 до mi # 8722; 1, i # 8712; 1: k. Тоді кожен елемент прямого твори M1 # 215; M2 # 215; ... # 215; Mk можна уявити як послідовність невід'ємних чисел r1, r2, ..., rk, де 0 # 8804; ri
num (r1, r2, ..., rk) = # 8721; i = 1: k ri # 215; # 8719; j = 1: i # 8722; 1 mj.
перестановки
Перестановка n-елементного безлічі X - це взаємно однозначна функція f: X → X. Якщо для простоти прийняти X =, то перестановкою можна назвати упорядкований набір з n різних чисел, що лежать в проміжку від 1 до n (далі буде розглядатися саме цей випадок).
Позначимо множину всіх перестановок безлічі X через Sn. Зрозуміло, що | Sn | = N. т. к. на перше місце набору можна поставити будь-яке число з n можливих, на друге - будь-яка з n # 8722; 1 залишилися і т. д. до останньої позиції, в яку ми поміщаємо останній залишився елемент: в результаті, ми отримаємо твір , яке і буде факторіалом n.
Розглянемо безліч Mi з попередньої частини. Нехай кожне Mi буде являти собою безліч чисел від 0 до i # 8722; 1. Позначимо через Tn твір n таких множин. Тоді якщо буде існувати взаимнооднозначное відповідність між Sn і Tn, то ми зможемо, зокрема, перенумерувати всі перестановки Sn. Висунемо механізм переходу від перестановки r1, ..., rn # 8712; Sn до елементу t1, ..., tn # 8712; Tn. Для цього для будь-якого i # 8712; 1: n знайдемо номер позиції s значення i в перестановці (rs = i) і приймемо в якості ti кількість елементів менших i серед r1, ..., rs # 8722; 1. А при зворотному переході від елемента до перестановки, можна використовувати те, що місце будь-якого елементу i (починаючи з самого великого) на одиницю більше, ніж число елементів, що передують i, а саме це число дорівнює сумі ti і числа елементів, більших i.
Крім того, кожну перестановку f # 8712; Sn можна уявити за допомогою орієнтованого графа з безліччю вершин X =, в якому ребро йде від x до у, коли f (x) = y. Легко можна показати, що такий граф складається з деякого числа елементарних циклів з різними множинами вершин, які в сумі дають безліч X. Т. е. Кожну перестановку ми можемо розкласти на цикли. Наприклад, розглянемо перестановку f (1234567) = 7514236 і розіб'ємо її на цикли:
генерування перестановок
Введемо деякі позначення для запису алгоритмів. Елементи перестановки будемо запам'ятовувати у вигляді елементів масиву P [1], ..., P [n]. Обмін значеннями змінних будемо позначати через P [i]: =: P [j]. Нагадаємо, що ми розглядаємо тільки перестановки, задані на множині X =.
На безлічі Sn задамо лексикографічний порядок:
(X1, ..., xn) <(y1, …, yn) ⇔ существует k ≥ 1, такое что xk ≤ yk и xl = yl для каждого l
(X1, ..., xn) <(y1, …, yn) ⇔ существует k ≤ n, такое что xk> yk і xl = yl для кожного l> k.
Тепер уявімо алгоритм генерації всіх перестановок в антілексікографіческом порядку. Зауважимо, що цей алгоритм є рекурсивним.
1 procedure REVERSE (m);
2 begin i: = 1; j: = m;
3 while i
5 end
6 end
7 procedure ANTYLEX (m);
8 begin
9 if m = 1 then
10 write (P [1], ..., P [n])
11 else
12 for i: = 1 to m do
13 begin ANTYLEX (m # 8722; 1);
14 if i
16 end
17 end
18 end;
19 begin
20 for i: = 1 to n do P [i]: =: i;
21 ANTYLEX (n)
22 end
Середнє число транспозиція, що припадають на кожну перестановку, приблизно дорівнює 1.543, тобто. Е. Для породження n! перестановок використовується приблизно 3.077n! порівнянь.
Можна запропонувати більш швидкий алгоритм, в якому кожна наступна перестановка утворюється з попередньої за допомогою тільки однієї транспозиції. Наведемо алгоритм генерації перестановок за мінімальне число транспозиція:
1 procedure B (m, i);
2 begin
3 if (m mod 2 = 0) and (m> 2) then
4 if i
6 else B: = m # 8722; 1
7 end;
8 procedure PERM (m);
9 begin
10 if m = 1 then
11 write (P [1], ..., P [n])
12 else
13 for i: = 1 to m do
14 begin PERM (m # 8722; 1);
15 if i
17 end;
18 begin
19 for i: = 1 to n do P [i]: =: i;
20 PERM (n)
21 end
Доведення коректності алгоритму можна знайти в [1].
Однак, існує ще більш швидкий алгоритм генерування перестановок, він будує послідовність перестановок, в якій кожна наступна утворюється з попередньої за допомогою одноразової транспозиції сусідніх елементів. Позначимо через PR [i] булеву змінну, що містить інформацію про те, чи переноситься елемент i вперед (PR [i] = true) або назад. Переменнная C [i] буде показувати, яку з можливих n # 8722; i + 1 позицій елемент i займає щодо елементів i + 1, ..., n на своєму шляху вперед і назад. Ось його код:
1 begin
2 for i: = 1 to n do
3 begin P [i]: = i; C [i]: = 1; PR [i]: = true;
4 end;
5 C [n]: = 0;
6 write (P [1], ..., P [n]);
7 i: = 1;
8 while i
10 while C [i] = n # 8722; i + 1 do
11 begin PR [i]: = not PR [i]; C [i]: = 1;
12 if PR [i] then x: = x + 1;
13 i: = i + 1;
14 end;
15 if i
17 if PR [i] then k: = C [i] + x;
18 else k: = n # 8722; i + 1 # 8722; C [i] + x;
19 P [k]: =: P [k + 1];
20 write (P [1], ..., P [n]);
21 C [i]: = C [i] + 1
22 end
23 end
24 end
На цю тему можна подивитися візуалізатори [3] і [4].
Послідовність перестановок, отримана за допомогою даного алгоритму має цікаву інтерпретацію. Так, якщо розглянути граф, вешіни якого відповідають усім перестановок і в якому дві вершини, відповідні перестановок f і g, з'єднані ребром, якщо g утворюється з f одноразової транспозицией сусідніх елементів, то отримана послідовність є гамільтоновим шляхом в цьому графі. На малюнку зображений граф послідовності для n = 3, 4.
Завдання про мінімумі скалярного твори
Перстановкі часто зустрічаються в самих різних областях математики і використовуються в різних завданнях. Наприклад, можна розглянути неалгебраїчні використання перестановки в наступній екстремальну задачу: дані 2m чисел x1, ..., xm і y1, ..., ym, потрібно знайти таке розбиття чисел на пари (xi, yj), при якому значення суми, складеної з творів чисел кожної пари, буде найменшим.
Нескладно показати, що рішення даного завдання досягається при зіставленні зростаючої послідовності xi і спадної послідовності yi, т. Е. Послідовностей, упорядкованих в протилежному порядку.
Розміщення і поєднання
Розміщення з n елементів по m - це упорядкований (тут нам важливий порядок) набір з m різних чисел, що лежать в проміжку від 1 до n (т. Е. # 8712; X). Іншими словами розміщення - це безліч з повтореннями. Позначимо число його елементів через An, m.
Для того, щоб обчислити значення An, m, потрібно слідувати тим же міркувань, що і у випадку з перестановками. Тоді отримаємо наступний результат:
An, m = n! # 8260; (N # 8722; m)!
Перебір і нумерація розміщень в цілому схожі з відповідними діями з перестановками. Розгляд цих питань пропонується Новомосковсктелю як корисний вправи.
Поєднання з n елементів по m - це невпорядкований набір (безліч) з m різних чисел, що належать безлічі X. Позначимо число елементів безлічі поєднань через Cn, m.
Т. к. Поєднання є неврегульованим набором, то кожному такому набору відповідає m! розміщень (т. е. упорядкованих набору тих же елементів). Тоді отримуємо, що
Cn, m = n! # 8260; m! (n # 8722; m)!
Можна навести деякі властивості поєднань:
1. Cn, m = Cn, n # 8722; m
2. Cn, m + Cn, m + 1 = Cn + 1, m + 1
3. Cn, m * Cm, k = Cn, k * Cn # 8722; k, m # 8722; k
Ці властивості випливають з самих визначень і перевіряються безпосередньо.
Тепер наведемо алгоритм генерації сполучень в лексикографічному порядку:
1 begin
2 for i: = 1 to k do A [i]: = i;
3 p: = k;
4 while p # 8804; 1 do
5 begin write (A [1], ..., A [k]);
6 if A [k] = n then p: = p # 8722; 1 else p: = k;
7 if p # 8805; 1 then
8 for i: = k downto p do A [i]: = A [p] + i # 8722; p + 1
9 end
10 end
Доступний визуализатор [5] даного алгоритму.
Нумерацію поєднань можна організувати, використовуючи властивість 2) поєднань, наведене вище. Для цього з кожним поєднанням з n по m зв'яжемо вектор з n нулів і одиниць. У цьому векторі буде m одиниць, а числа поєднання будуть задавати номери цих одиниць. Тоді такого вектору можна, в свою чергу, зіставити траєкторію, в якій одиницям відповідають горизонтальний кроки, а нулях - вертикальні. Тоді формула для номера буде вигляеть, як
num (b [1: n], m) = <если b[n] = 0, то num(b[1:n−1], m); если b[n] = 1, то Cn−1,m + num(b[1:n−1], m−1)>,
де b [1: n] - 0-1 вектор з n елементів.
Біном Ньютона
Якщо в вузлах позитивного квадранта прямокутної координатної решітки помістити кількість шляхів від початку координат до цих вузлів і повернути цю решітку так, щоб початок координат було нагорі, то ми отримаємо трикутник Паскаля:
З цього трикутника зручно вважати число поєднань для невеликих параметрів. Крім того, до цієї схеми пов'язана формула бінома Ньютона:
(A + b) n = # 8721; k = 0: n Cn, kakbn # 8722; k
У цій формулі при розкритті ступеня алгебраїчного двочлена коефіцієнти при ступенях збігаються з числом сполучень. Виходячи з формули Ньютона значення Cn, m також ще називають біноміальними коефіцієнтами. Деякі цікаві властивості бинома Ньютона розглянуті в [2].