Метод Гергели построения диагональных латинских квадратов
В [1] описывается метод построения диагональных латинских квадратов. Ниже вольный перевод этой статьи.

В методе используются трансверсали (transversal), поэтому, прежде всего, определение: трансверсаль квадрата - это коллекция n его элементов, таких, что все они расположены в разных строках, колонках и содержат ровно по одному разу все элементы используемого множества чисел. Пример трансверсалей для квадрата порядка 4:

 1
 2
 3
 4
 3
 4
 1
 2
 4
 3
 2
 1
 2
 1
 4
 3

 1
 2
 3
 4
 3
 4
 1
 2
 4
 3
 2
 1
 2
 1
 4
 3


Так вот, если обе диагонали квадрата образуют трансверсаль, латинский квадрат называется диагональным (doubly diagonalized). (Квадрат, у которого только главная диагональ образует трансверсаль, в статье называется diagonalized. Поскольку диагональным мы называем квадрат с двумя диагоналями, для квадрата с одной диагональю оставим английский термин diagonalized.)

Лемма: Для любого n ≥ 3 существует diagonalized латинский квадрат порядка n, в котором есть трансверсаль, не имеющая общих элементов с главной диагональю.

Доказательство делится на три части.

Для нечетного n циклический латинский квадрат (мультипликативная таблица циклических групп порядка n) может быть сформирован как сумма из n трансверсалей, одна из которых главная диагональ. Например, для n = 3 и множества символов {1,2,3}

      1 2 3   |1    |     |  2  |     |    3|   
 C3 = 2 3 1 = |  3  |  +  |    1|  +  |2    |   
      3 1 2   |    2|     |3    |     |  1  |   


Для порядков 4 и 6 просто приводится пара таких квадратов:

 1 2 3 4 
 3 4 1 2 
 4 3 2 1 
 2 1 4 3 

 1 2 3 4 5 6 
 5 3 6 1 4 2 
 4 1 5 2 6 3 
 2 4 1 6 3 5 
 6 5 4 3 2 1 
 3 6 2 5 1 4 

Наконец, для четных n ≥ 8 такой квадрат строится из двух циклических латинских квадратов.

  ------------------ ......
 |                  |      .
 |                  |      .
 |                  |      .
 |      C n-3       |      .
 |                  |      .
 |                  |      .
 |                  |      .
 |                  |      .
 |                  |      .
  ------------------ ------
 .                  |      |
 .                  |  C3  |
 .                  |      |
  .................. ------

Первый квадрат Cn-3 порядка n-3 из символов {1 … n-3}, второй C3 порядка 3 из символов {n-2, n-1, n}. Чтобы заполнить пустые области, выбираем трансверсали квадрата Cn-3 (кроме главной диагонали) и выполняем следующее:

Для трансверсали проектируем ее символы вертикально на свободную строку и горизонтально на свободную колонку и заменяем все символы выбранной трансверсали на n-2.

Повторяем эту процедуру еще для двух трансверсалей, заменяя их символы на n-1 и n .

В результате мы получим diagonalized латинский квадрат из символов {1 … n} . И, поскольку заменены только три трансверсали, существует еще (n-3)-32 трансверсалей, отличных от главной диагонали.

Можно использовать любое деление квадратов на части n = (n-m) + m , где m - нечетное и 3 < m < n-m.

Теорема Для любого n ≥ 4 существует диагональный латинский квадрат порядка n.

Будем строить диагональный латинский квадрат из 4-х латинских квадрата D1, D2, D3, D4 порядка k ≥ 2. Рассмотрим отдельно два случая - для четных n = 2k и для нечетных n = 2k+1:

      n = 2*k                    n = 2*k+1

  ------- -------            -------   -------   
 |       |       |          |       | |       |  
 |  D1   |  D2   | k        |  D1   | |  D2   | k
 |       |       |          |       | |       |  
  ------- -------            -------   -------   
 |       |       |           -------   -------  1
 |  D4   |  D3   | k        |       | |       |
 |       |       |          |  D4   | |  D3   | k
  ------- -------           |       | |       |
     k       k               -------   -------
                                k    1    k

Берем квадрат D1, удовлетворяющий лемме. Квадрат D2 строим из него отражением по вертикали и каждый элемент заменяем на (x+k) mod 2k

D1 = C5
D2
 1 2 3 4 5 
 0 9 8 7 6 
 2 3 4 5 1 
 6 0 9 8 7 
 3 4 5 1 2 
 7 6 0 9 8 
 4 5 1 2 3 
 8 7 6 0 9 
 5 1 2 3 4 
 9 8 7 6 0 

Квадрат D3 получаем из квадрата D1. Для этого записываем в обратном порядке элементы главной диагонали, а под ними проектируем элементы тансверсали. Полученные пары символов используем для замены элементов в квадрате D1. Квадрат D4 получаем из квадрата D2 аналогично.

D1
D2
 1 2 3 4 5 
 2 3 4 5 1 
 3 4 5 1 2 
 4 5 1 2 3 
 5 1 2 3 4 
 0 9 8 7 6 
 6 0 9 8 7 
 7 6 0 9 8 
 8 7 6 0 9 
 9 8 7 6 0 
 4 2 5 3 1 
 5 2 4 1 3 
 6 8 0 7 9 
 8 6 9 7 0 
 3 2 1 5 4 
 2 1 5 4 3 
 1 5 4 3 2 
 5 4 3 2 1 
 4 3 2 1 5 
 9 0 6 7 8 
 8 9 0 6 7 
 7 8 9 0 6 
 6 7 8 9 0 
 0 6 7 8 9 
D3
D4

Для итогового квадрата порядка 2k меняем верхние трансверсали и нижние диагонали:

 1 7 3 4 5 
 2 3 9 5 1 
 3 4 5 6 2 
 4 5 1 2 8 
 0 1 2 3 4 
 0 9 8 2 6 
 6 0 4 8 7 
 7 1 0 9 8 
 3 7 6 0 9 
 9 8 7 6 5 
 9 0 6 7 3 
 8 9 0 1 7 
 7 8 4 0 6 
 6 2 8 9 0 
 5 6 7 8 9 
 8 2 1 5 4 
 2 6 5 4 3 
 1 5 9 3 2 
 5 4 3 7 1 
 4 3 2 1 0 

Для итогового квадрата порядка 2k+1, как и в первом случае меняем местами верхние трансверсали и нижние диагонали. Затем трансверсали квадратов D1 и D3 проецируем на среднюю строку и колонку и заменяем на n. Центральный элемент тоже равен n.

 1 . 3 4 5 
 2 3 . 5 1 
 3 4 5 . 2 
 4 5 1 2 . 
 . 1 2 3 4 
 7 
 9 
 6 
 8 
 0 
 0 9 8 2 6 
 6 0 4 8 7 
 7 1 0 9 8 
 3 7 6 0 9 
 9 8 7 6 5 
 0 7 9 6 8 
 . 
 4 2 5 3 1 
 9 0 6 7 3 
 8 9 0 1 7 
 7 8 4 0 6 
 6 2 8 9 0 
 5 6 7 8 9 
 2 
 5 
 3 
 1 
 4 
 8 . 1 5 4 
 2 6 . 4 3 
 1 5 9 . 2 
 5 4 3 7 . 
 . 3 2 1 0 

1Ervin Gergely. A Simple Method for Constructing Doubly Diagonalized Latin Squares. 1972.

В приложении исходники описанного алгоритма и приложение для построения диагонального латинского квадрата. (Порядок квадрата задается как параметр)
Downloads
Исходники и приложение (Windows/Delphi) для получения DLS (testDLK.zip) (31.8 Кб, просмотров: 721 )

Comments
17.02.2016 11:27 Наталия
 Здравствуйте, Алексей!
 приглашаю вас в мощный российский проект по ортогональным латинским 
 квадратам 10-го порядка на платформе BOINC.
 Проект SAT@home
 А также в мою тему на форуме сайта boinc.ru
 Думаю, вам будет интересно.
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by