Латинські квадрати мають довгу історію, висхідну до Л. Ейлера. Вони виникають в задачах теорії груп та напівгруп, кодування, складання розкладів, розподілу ресурсів, черговості ініціювання подій, видачі студентам завдань і т.п. [55, c.261 - 282]. В даний час латинські квадрати знову стають об'єктом активних досліджень в зв'язку з невирішеними проблемами кінцевих геометрій.
Визначення. Латинським квадратом порядку n називають квадратну матрицю m розміром n 'n. елементи якої належать множині M = n>, причому кожне число з M зустрічається рівно один раз в кожному рядку і в кожному стовпці m.
З визначення латинського квадрата випливає, що рядки m складаються з різних перестановок чисел від 1 до n. Стовпці m також складаються з різних перестановок цих чисел.
Як приклад, що приводить до латинських квадратах, розглянемо спрощену задачу про складання розкладу. Нехай п'ять викладачів Pi (i = 1, 2. 5) школи протягом п'яти послідовних уроків повинні провести заняття в п'яти класах Kj (j = 1, 2. 5). При цьому кожен з викладачів зобов'язаний дати один урок в кожному класі. У цій ситуації виявляється, існує 1344 можливих різних розкладів. Нижче наведено одне з них:
Елементи m інтерпретуються тут так. Викладач Pi (i = 1, 2. 5) проводить заняття в класі Kj (j = 1, 2. 5) на уроці номер mi, j.
Нижче на основі алгоритму перебору з поверненням будуть побудовані рекурсивні функції підрахунку загальної кількості і генерування сукупності латинських квадратів розміром n 'n. При цьому в якості будівельного матеріалу для їх отримання буде використовуватися послідовність P всіх перестановок з елементів, представлена в лексикографічному порядку.
Нагадаємо, що лексикографічний порядок на P вводиться так. нехай
і для знака лексикографічного порівняння перестановок використовується символ <’ (меньше). Тогда считают, что:
На малюнку 4 по стовпцях в лексикографічному порядку виписані всі перестановки для n = 4. У загальному випадку формувати їх можна за допомогою спеціальної рекурсивної функції (див. Розділ "Перестановки"). При лексикографічної формі записи послідовність перестановок P представляється у вигляді окремих блоків по (n - 1)! елементів в кожному. Якщо пронумерувати ці блоки від 0 до (n - 1), то все перестановки блоку j (j = 0, 1, ..., n - 1) будуть починатися з цифри (j +1). Надалі цей факт буде використаний при організації рекурсії.
Можна вважати, що елементи нульової рядки будь-якого формується латинського квадрата L є послідовні цифри від 1 до n. При цих угодах j -й стовпець для L є просто одна з перестановок j -го блоку P (j = 0, 1, ..., n -1). Отже, можливий такий механізм формування або підрахунку кількості всіх латинських квадратів розміром n 'n.
Мал. 4. Схема формування латинського квадрата з перестановок
Будуємо чергову матрицю-кандидат L. формуючи кожен її j -й стовпець з будь-якої перестановки j -го блоку P (j = 0,1, ..., n - 1). Якщо L є латинським квадратом, то запам'ятовуємо або виводимо його.Якщо перебрані не всі матриці-кандидати, то повертаємося до пункту 1, інакше організовуємо висновок результату (якщо потрібно) і обчислення припиняємо.
Подібний повний перебір всіх можливих кандидатів досить трудомісткий. Однак запропоновану схему цілком можна використовувати для організації перебору з поверненням, відразу ж відмітати багатьох кандидатів до їх повної побудови. Це і зроблено нижче.
Адачі 5. Кількість латинських квадратів. Написати рекурсивну програму-функцію, яка при заданому натуральному n методом перебору з поверненням підраховує кількість латинських квадратів розміром n 'n з першим рядком виду: 1. 2, ..., n.
Рішення. Нехай P - послідовність перестановок в лексикографічному порядку з елементів n> з n виділеними блоками (див. Вище). Функції Lanum (n) і Latinu (n, fa, mpos, ot, j) вирішують поставлене завдання.
Головний функція Lanum (n) по заданому n готує фактичні аргументи для рекурсивної функції Latinu ():
n - розмір квадрата і кількість блоків в P;
j - рівень рекурсивного виклику і номер блоку послідовності перестановок P.
Зупинимося докладніше на алгоритмі, що реалізується функцією Latinu (), і динаміці заповнення матриці mpos нулями і одиницями. На малюнку 4 з методичних міркувань в mpos замість реальних одиниць проставлені їх замінюють символи: #, , $ І%. Це дає можливість наочно простежити за відповідністю фіксуються перестановок в кожному з блоків P і заповненням mpos одиницями.
Перш за все, відзначимо, що рекурсія організована за номером j поточного блоку P. з якого і вибирається черговий стовпець для створюваного латинського квадрата L. Нехай ми знаходимося в j -му рекурсивном виклик, тобто для побудови L вже обрані перестановки з 0,1, ..., (j - 1) -го блоків P і зафіксований деякий стовпець t з j -го блоку P. окремо розглянемо такі можливі взаємовиключні випадки:
A. Позиції (s. Ps, t - 1) (s = 0, 1. n -1) матриці mpos встановлені в нуль (сума відповідних елементів дорівнює нулю):
B. По крайней мере, одна з позицій (s. Ps, t - 1) (s = 1, 2. n -1) матриці mpos встановлена в одиницю.
Нехай справедливим є твердження A. Тоді виконуються наступні дії. Позиції (s. Ps, t - 1) (s = 1, 2. n -1) матриці mpos переустановлюються в одиницю:
і стовпець j під'єднується до формованому квадрату. Далі, якщо j Нехай справедливим є твердження B. Тоді виконуються такі дії. У поточному j -м блоці P здійснюється перехід до наступного колонки, як до чергового кандидата на включення в L. і знову реалізується одна з альтернатив A або B. Якщо j> 0 і j -й блок P вичерпаний, то здійснюється повернення з поточного рекурсивного виклику. Після цього елементи mpos. встановлені в (j - 1) -м рекурсивном виклик в одиницю, переустановлюються в нуль. Якщо j = 0 і j -й блок P вичерпаний, то функція Latinu () повертає обчислене значення ot. Зауваження. Розглянуту задачу можна було б вирішувати більш ефективно. Наприклад, так. Нехай функція Latinu () формує лише латинські квадрати з нульовою рядком і нульовим стовпцем виду 1, 2, ..., n. Якщо їх кількість виявиться рівним m. то рішенням завдання, очевидно, буде число m × (n - 1) !. Для реалізації цієї схеми досить зафіксувати початкову перестановку нульового блоку P і не змінювати її в процесі обчислень, що відповідає організації рекурсії ні з нульового, а з першого блоку P. Домогтися цього можна наступній незначною модифікацією функції Lanum (): Контрольні приклади. У таблиці вказано кількість латинських квадратів для значень n від двох до шести. Розрахунок проведено за функцією Lanumq (n). Адачі 6. Латинські квадрати. Написати рекурсивну функцію, яка при заданому натуральному n формує і виводить латинські квадрати розміром n 'n з нульовою рядком і нульовим стовпцем виду: 1, 2, ..., n. Рішення. При зазначених в умовах завдання угодах j -й стовпець будь-якого формується латинського квадрата L повинен вибиратися з j -го блоку матриці перестановок P (j = 0,1, ... n - 1). При цьому нульовий стовпець L завжди повинен збігатися з нульовим стовпцем нульового блоку P. З метою економії пам'яті відповідь будемо формувати у вигляді матриці ot. кожен стовпець k (k = 0,1, ...) якої кодує конкретний латинський квадрат L за такою схемою. Значення елемента oti, k (i = 0, 1. n -1) - це номер i-го стовпця L в матриці P (див. Рис.5). Рішенням задачі можуть служити функції Latin () і Lainitq (). Обчислення по ним проводяться майже так само, як і по парі раніше розглянутих функцій Latinu () і Lanumq (). Основні відмінності тут такі. Функція Latin () в порівнянні з Latinu () має додатковий формальний параметр-вектор new. Він служить для покомпонентного запам'ятовування коду чергового формованого латинського квадрата L у вигляді послідовних номерів стовпців P. Кожен знову сформований вектор new приєднується справа до матриці відповідей ot (в Latinu () ot була простою змінною). Рекурсія в функції Latin () організована, як і в функції Latinu (), за номером j поточного блоку матриці перестановок P. Контрольні приклади. Нижче обчислено значення функції Lainitq (4) і праворуч від отриманої матриці наведені відповідні її стовпцями латинські квадрати. Мал. 5. Відповідність стовпців матриці відповідей і латинських квадратів Зауваження. Щоб функція Latin () при заданому натуральному n обчислювала все латинські квадрати розміром n 'n з нульовою рядком виду: 1, 2, .... n і без обмежень на нульовий стовпець, досить злегка модифікувати головний програму Lainitq (). Її нова редакція може бути такою:Схожі статті