Перестановки Нехай задано безліч з n елементів. Впорядкування цих елементів називається перестановкою. Іноді додають «з n елементів». Зазвичай виділяється одне, основне або природне, впорядкування, яке називається тривіальною перестановкою. Самі елементи множини A нас не цікавлять. Часто в якості елементів беруть цілі числа від 1 до n або від 0 до n-1. Позначимо безліч перестановок з n елементів через Pn. а його потужність через Pn. Задамо все ті ж три питання: чому дорівнює Pn, як перебрати елементи Pn. як їх перенумерувати.
Теорема про число перестановок Число перестановок з n елементів дорівнює n! - твору чисел від 1 до n. (N! Читається n-факторіал) Доказ. За індукції. Для n = 1 формула очевидно вірна. Нехай вона вірна для n-1, доведемо, що вона вірна і для n. Перший елемент упорядкування можна вибрати n способами, а до вибраного першому елементу можна способами приписати інше. Тому правильна формула Pn = Pn-1 n. Якщо Pn-1 = (n-1). то Pn = n!
Нумерація перестановок Щоб нумерувати перестановки, ми відобразимо безліч Pn взаимнооднозначное в інше безліч Tn, на якому ввести нумерацію буде набагато простіше, а потім для будь-якого елемента p Pn як його номера візьмемо номер його образу в Tn. Безліч Tn- це пряме твір декількох числових відрізків Tn = (0: (n-1)) (0: (n-2) .... Тобто кожен елемент Tn- це набір невід'ємних чисел i1, i2, ..., in- 1, in, причому ik nk.
Відображення Візьмемо перестановку і випишемо поруч з нею тривіальну перестановку. В якості першого індексу візьмемо місце першого елемента (рахуючи від нуля) в тривіальної перестановці. Запишемо замість тривіальної перестановки рядок символів, що залишились. В якості другого індексу візьмемо місце другого елементу перестановки в цьому рядку. Повторимо процес до кінця. Очевидно, що k-й індекс буде менше довжини k-го рядка, а останній індекс дорівнюватиме нулю. Подивимося цей процес на прикладі.
Приклад відображення 0 1 2 3 4 5 6 Індекс cadfgbeabcdefg 2 2 adfgbeabdefg 0 2 0 dfgbebdefg 1 2 0 1 fgbebefg 2 2 0 1 2 gbebeg 2 2 0 1 2 2 bebe 0 2 0 1 2 2 0 ee 0 2 0 1 2 2 0 0 Очевидно, що цей процес звернемо і зворотне відображення побудує по набору індексів вихідну перестановку.
Нумерація безлічі Tn Будь-яке пряме твір упорядкованих множин можна розглядати як систему числення з перемінним підставою. Згадайте приклад з секундами з першої лекції або розгляньте будь-яку стару шкалу розмірів: 1 ярд = 3 фути, 1 фут = 12 дюймів, 1 дюйм = 12 ліній, 1 лінія = 6 пунктів. (2, 0, 4, 2, 3) = 2 ярда 0 футів 4 дюйми 2 лінії 3 пункту, скільки ж це пунктів? Потрібно порахувати (це називається схемою Горнера) (((2 3 + 0) 12 + 4) 12 + 2) 6 + 3
Нумерація безлічі Tn - 2 Формулу #, що знаходить номер для набору індексів i1, i2, ..., in-1, in, ми віддамо перевагу написати у вигляді рекурентних виразів # (i1, i2, ..., in) = a (i1, i2, ... , in-1, n-1); a (i1, i2, ..., ik, k) = a (i1, i2, ..., ik-1, k-1) (n-k + 1) + ik; a (порожньо, 0) = 0; За цією формулою # (2,0,1,2,2,0,0) = a (2,0,1,2,2,0,6). Маємо a (2,1) = 2; a (2,0,2) = 2 6 + 0 = 12; a (2,0,1,3) = 12 5 + 1 = 61; a (2,0,1,2,4) = 61 4 + 2 = 246; a (2,0,1,2,2,5) = 246 3 + 2 = 740; a (2,0,1,2,2,0,6) = 740 2 + 0 = 1480;
Перебір наборів індексів Виходячи з вищевикладеного, перебрати перестановки просто: потрібно перебрати всі набори індексів з і по кожному набору будувати відповідну йому перестановку. Для перебору наборів індексів зауважимо, що фактично кожен набір - це запис числа в особливій системі числення з перемінним підставою (система називається факторіальною). Правила додавання 1 в цій системі майже так само прості, як в двійковій: рухаючись від останнього розряду намагатися додати в поточному розряді 1. Якщо це можливо, то додавши 1 зупинитися. Якщо неможливо, записати в розряд нуль і перейти до наступного розряду.
Перебір наборів індексів - 2 Розглянемо приклад: 7 6 5 4 3 2 1 Це змінні підстави 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Зверніть увагу, що в 3 4 4 2 2 1 0 кожному рядку початок таке 3 4 4 3 0 0 0 ж, як у попередній, 3 4 4 3 0 1 0 потім йде елемент, строго 3 4 4 3 1 0 0 більший. а 3 4 4 3 1 1 0 подальше несуттєво. 3 4 4 3 2 0 0 Значить, кожен рядок 3 4 4 3 2 1 0 лексикографічно більше 3 5 0 0 0 0 0 попередньої. 3 5 0 0 0 1 0
Теорема про лексикографічному переборі перестановок Описаний алгоритм перебирає перестановки в порядку лексикографічного зростання. Доведення. Нам досить показати, що якщо ми маємо два набори індексів I1 і I2, і I1 лексикографічно передує I2, то перестановка (I1) лексикографічно передує (I2). Ці перестановки формуються послідовно, і поки збігаються I1 і I2, збігаються і їх перестановки. А більшого значення індексу відповідає і більший елемент.
Прямий алгоритм лексикографічного перебору перестановок Візьмемо будь-яку перестановку p і прямо знайдемо лексикографічно наступну. Візьмемо початок - перші k елементів. Серед його продовжень відомі мінімальне, в якому всі елементи розташовані по зростанню, і максимальне, в якому по спадаючій. Наприклад, в перестановці p = (4, 2, 1, 7, 3, 6, 5) всі продовження для (4, 2, 1) лежать між (3, 5, 6, 7) і (7, 6, 5, 3). Наявне продовження менше максимального, і 3-й елемент ще можна не змінювати. І 4-й теж. А 5-й потрібно змінити. Для цього з решти елементів потрібно взяти наступний усе своєю чергою, поставити його 5-м і приписати мінімальне продовження. Вийде (4, 2, 1, 7, 5, 3, 6).
Прямий алгоритм лексикографічного перебору перестановок - 2 випишемо кілька наступних перестановок. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6 , 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)
Формальний опис алгоритму Стан роботи: Перестановка p і логічний ознака isActive. Початковий стан: В записана тривіальна перестановка і isActive = True. Стандартний крок: Якщо isActive, видати перестановку в якості результату. Рухаючись з кінця, знайти в перестановці найбільший монотонно спадною суфікс. Нехай k - позиція перед суфіксом. Покласти isActive: = (k gt; 0). Якщо isActive, то знайти в суфіксі найменший елемент, що перевершує pk, поміняти його місцями з pk, а потім суфікс «перевернути».
Ще алгоритм перебору перестановок Спробуємо тепер перебрати перестановки так, щоб дві послідовні перестановки мало відрізнялися один від одного. Наскільки мало? На одну елементарну транспозицию, в якій міняються місцями два сусідніх елемента. Чи це можливо? Покажемо принципову схему такого алгоритму, нам буде цікава саме вона. Уявіть собі n-1 елементарних «механізмів», кожен з пересуває свій елемент всередині набору. На кожному кроці механізм робить зрушення наліво або направо. Напрямок змінюється, коли елемент доходить до краю. На зміну напрямку витрачається один крок, під час якого крок робить наступний механізм, який, втім, теж може змінювати напрямок.
Ще алгоритм перебору перестановок -2 Подивимося приклад. 1 2 3 4 5 Чий хід 1 2 3 4 5 Чий хід a b c d e a c d a b e a b a c d e a c d b a e a b c a d e a c d b e a b b c d a e a c d e b a a b c d e a b c d e a b a c b d e a a c d a e b a c b d a e a c a d e b a c b a d e a a c d e b c c a b d e a a d c e b a a c b d e b d a c e b a a c d b e a d c a e b a c a d b e a d c e a b a
Перебір перестановок. 1 function ExistsNextPerm (var kCh: integer): Boolean; var iV, iP, iVC, iPC: integer; begin result: = False; for iV: = nV downto 2 do if count [iV] lt; iV-1 then begin Inc (count [iV]); iP: = pos [iV]; iPC: = iP + dir [iV]; iVC: = perm [iPC]; perm [iP]: = iVC; perm [iPC]: = iV; pos [iVC]: = iP; pos [iV]: = iPC; kCh: = iP; if dir [iV] lt; 0 then Dec (kCh); result: = True; exit; end else begin count [iV]: = 0; dir [iV]: = - dir [iV]; end; end;
Завдання про мінімумі суми попарних творів Нехай задані два набори по n чисел, скажімо, і. Ці числа розбиваються на пари (ak, bk) і обчислюється сума їх попарних творів k 1: n akbk. Можна міняти нумерацію і. Потрібно вибрати таку нумерацію, при якій сума є мінімальною. У цьому завданні можна зафіксувати якісь нумерації і і шукати перестановку. для якої досягається мінімум суми k 1: n akb (k). Ми виберемо нумерації, коли розташовані по зростанню, а - по спадаючій.
Теорема про мінімум суми попарних творів Мінімум суми попарних творів досягається на тривіальної перестановці. Доведення. Припустимо, що існують такі два індексу k і r, що ak lt; ar і bk lt; br. У цьому випадку (ar ak) (br bk) gt; 0, тобто ar br + ak bk gt; ar bk + ak br. В нашій нумерації розташовані по зростанню. Якщо розташовані не по зростанню, то знайдеться така пара k і r, як сказано вище. Переставивши у цієї пари bk і br. ми зменшимо значення суми. Значить, в оптимальному вирішенні стоять по зростанню. Ця проста теорема кілька разів зустрінеться нам надалі.
Завдання про максимальну зростаючої підпослідовності Задана послідовність чисел довжини n. Потрібно знайти її послідовність максимальної довжини, в якій числа йшли б в зростаючому порядку. Наприклад, в послідовності 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 максимальної буде підпослідовність 2, 11, 14, 16, 17, 25, 37, 41 С перестановками ця задача пов'язана тим, що вихідна послідовність може бути перестановкою. Ми обмежимося тим, що покажемо, як вирішується це завдання, а формалізацію і обгрунтування алгоритму надамо слухачам.
Знаходження максимальної зростаючої підпослідовності Будемо по можливості економно розбивати нашу на убутні послідовності (приклад змінений) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6 5 12 11 8 7 14 13 18 16 15 17 37 19 21 Кожне наступне число пишеться в саму верхню з рядків, де воно не порушить порядку. Візьмемо число з нижньої строчки, 21. Чому воно коштує в 8-му рядку? Йому заважає 19. А числу 19 заважає 17. А йому 16. І т. Д. Послідовність 9, 11, 14, 16, 17, 19, 21 зростає і має довжину 7. Будь-яка послідовність більшої довжини містить два числа з одного рядка ( принцип Дирихле) і не може бути зростаючій.
Завдання про мінімальне число інверсій Задана послідовність чисел довжини n. Інверсією назвемо виконується на місці дзеркальне відображення будь-якої її підрядка - суцільний подпоследовательності.Требуется за мінімальне число інверсій розташувати елементи послідовності по зростанню. Наприклад, перестановку «суцільна» можна перетворювати так (червоні літери переставлені, великі вже стоять на місці) суцільні сплоанШЯ наолПСШЯ АнолПСШЯ АнлОПСШЯ АЛНОПСШЯ (за п'ять інверсій)
Екзаменаційні питання Перестановки. Їх перебір і нумерація. Завдання про мінімумі скалярного твори. Завдання про найбільшу зростаючої підпослідовності.
Завдання 1. Двосторонній перехід перестановка число 2. Знайти перестановку, що відстоїть від даної на дане число кроків. 3. Перебір перестановок елементарними транспозиція. 4. Виконати приклад для завдання про мінімумі скалярного твори.