дискретний аналіз

Нехай задано якесь кінцеве безліч A з n елементів.

Будь-яке впорядкування цих елементів, т. Е. Розташування їх у будь-якої послідовності, називається перестановкою. Іноді додають «з n елементів». Зазвичай виділяється одне, основне або природне, впорядкування, яке називається тривіальною перестановкою.

Самі елементи множини A нас не цікавлять. Часто в якості розглянутих елементів беруть цілі числа від 1 до n або від 0 до n-1.

Позначимо безліч перестановок з n елементів через P n. а його потужність через Pn.

Задамо знайомі нам вже три питання: чому дорівнює Pn. як перебрати елементи P n. як їх перенумерувати.

Теорема про число перестановок

Теорема. Число перестановок з n елементів дорівнює n. - твору чисел від 1 до n.

(Позначення n. Новомосковскется ен-факторіал.)

Доведення. За індукції. Для n = 1 формула очевидно вірна.

Нехай вона вірна для n - 1. доведемо, що вона вірна і для n. Перший елемент упорядкування можна вибрати n способами, а до вибраного першому елементу можна Pn -1 способами приписати інше. Тому правильна формула Pn = n × Pn -1.
Якщо Pn -1 = (n -1). то Pn = (n)!

Для нумерування перестановки, ми відобразимо безліч P n взаимнооднозначное (побудуємо біекція) в іншу множину T n. на якому ввести нумерацію буде набагато простіше, а потім для будь-якого елемента p ∈ P n в якості його номера візьмемо номер його образу в T n.

Безліч T n - це пряме твір декількох числових відрізків

Отже, будуємо відображення.

Візьмемо перестановку і випишемо поруч з нею тривіальну перестановку. В якості першого індексу візьмемо місце першого елемента (рахуючи від нуля) в тривіальної перестановці. Запишемо замість тривіальної перестановки рядок символів, що залишились. В якості другого індексу візьмемо місце другого елементу перестановки в цьому рядку. Повторимо процес до кінця.

Очевидно, що k -й індекс буде менше довжини k -го рядка, а останній індекс дорівнюватиме нулю.

Подивимося цей процес на прикладі.

Очевидно, що цей процес звернемо і що зворотне відображення побудує по набору індексів вихідну перестановку.

Нумерація безлічі T n

Будь-яке пряме твір упорядкованих множин можна розглядати як систему числення з перемінним підставою. Згадайте приклад з секундами з першої лекції або розгляньте будь-яку стару шкалу розмірів:

1 ярд = 3 фути,
1 фут = 12 дюймів,
1 дюйм = 12 ліній,
1 лінія = 6 пунктів.

(2, 0, 4, 2, 3) = 2 ярда 0 футів 4 дюйми 2 лінії 3 пункту, скільки ж це пунктів?

Потрібно обчислити (це називається схемою Горнера) (((2 # 0180; 3 + 0) # 0180; 12 + 4) # 0180; 12 + 2) # 0180; 6 + 3.

Формулу #. сопоставляющую набору індексів i1. i2. ..., in -1. in його номер, ми віддамо перевагу написати у вигляді рекурентних виразів

За цією формулою # (2,0,1,2,2,0,0) = a (2,0,1,2,2,0,6).

a (2,1) = 2;
a (2,0,2) = 2 # 0180; 6 + 0 = 12;
a (2,0,1,3) = 12 # 0180; 5 + 1 = 61;
a (2,0,1,2,4) = 61 # 0180; 4 + 2 = 246;
a (2,0,1,2,2,5) = 246 # 0180; 3 + 2 = 740;
a (2,0,1,2,2,0,6) = 740 # 0180; 2 + 0 = 1480;

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

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

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