Метод Гергели построения диагональных латинских квадратов
В [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 Кб, просмотров: 779 )

Comments
17.02.2016 11:27 Наталия
 Здравствуйте, Алексей!
 приглашаю вас в мощный российский проект по ортогональным латинским 
 квадратам 10-го порядка на платформе BOINC.
 Проект SAT@home
 А также в мою тему на форуме сайта boinc.ru
 Думаю, вам будет интересно.
 
25.08.2017 02:26 Aboinendemia
  This condition is fairly limited by the reproductive system and might have several causes
  including a results of injury or abnormal the flow of blood inside the testicles.  Howeve
 r, it is important to have the doctor's opinion first before you take these oral medicatio
 ns since these might have pessimistic effects for the body.
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

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


Copyright © 2009-2014 by