ОДЛК. Метод Линдера
В статье Линдера[1] рассматривается метод построения пары ортогональных дважды диагональных латинских квадратов, основанный на операции сингулярное прямое произведение квазигрупп (singular direct product of quasigroups).

О математическом обосновании операции подробнее смотрите в статье. Здесь мы рассмотрим действия, которые необходимо проделать, при выполнении операции применительно к латинским квадратам. В общих чертах операция напоминает Кронекерово произведение (Kroneker product) матриц, но выполняется над тремя матрицами.

Пусть у нас есть три латриских квадрата: V - латинский квадрат порядка v на множестве {1,2, … v}, Q - латинский квадрат порядка q на множестве {1,2, … q}, левый верхний угол которого - тоже латинский квадрат P порядка p на множестве {1,2, … p} и P1 - латинский квадрат порядка q-p , на множестве {p+1, p+2, … q}.

Латинский квадрат Q можно разбить на следующие четыре части по границам квадрата P :

 P     

 Q1     

 Q2 

 Q3     


Обозначим операцию сингулярное прямое произведение (далее в тексте просто произведение) как V x Q(P, P1) . Такое произведение выполняется следующим образом.

Квадрат P становится ячейкой A(0,0) нового квадрата. Части Q1 , Q2 , Q3 квадрата Q записываем v раз (k=1 … v) в нулевой строке, нулевой колонке и диагонали нового квадрата соответственно, заменяя элементы x этих частей парой (x,k) . Для элементов квадрата P, расположенных на диагонали k=1 (или без пары).

 P 
 (Q1, 1) 
 (Q1, 2) 
 (Q1, v) 
 (Q2,1) 
 (Q3, 1) 
 (Q2,2) 
 (Q3, 2) 
 (Q2,v) 
 (Q3, v) 

В оставшиеся части нового квадрата A(i,j), i<>j, i<>0, j<>0 записываем квадрат P1, заменяя элементы x этого квадрата парой (x,vij), где vij - элемент (i,j) квадрата V.

 P 
 (Q1, 1) 
 (Q1, 2) 
 (Q1, v) 
 (Q2,1) 
 (Q3, 1) 
 (P1, v(1,2)) 
 (P1, v(1,v)) 
 (Q2,2) 
 (P1, v(2,1)) 
 (Q3, 2) 
 (P1, v(2,v)) 
 (Q2,v) 
 (P1, v(v,1)) 
 (P1, v(v,2)) 
 (Q3, v) 

В результате получаем латинский квадрат порядка v(q-p)+p.

Перейдем к конструированию дважды диагональных латинских квадратов. Пусть введенные выше квадраты имеют следующие свойства:

  • квадрат V - дважды диагональный четного порядка v = 2m
  • квадрат Q - диагональный (с одной главной диагональю)
  • квадрат P - дважды диагональный
  • квадрат P1 - диагональный (с одной побочной диагональю)

Условие четности порядка квадрата V позволяет разбить полученное произведение на части следующим образом:

 A(0,0) 
 A(0,1) 
 A(0,m) 
 A(0,m+1) 
 A(0,v) 
 A(1,0) 
 A1 
 A2 
 A(m,0) 
 A(m+1,0) 
 A3 
 A4 
 A(v,0) 

Из определения произведения видно, что для частей A1, A4 главная диагональ является трансверсалью, а для частей A2, A3 побочная диагональ является трансверсалью. Поэтому переставив части следующим образом:

 A4 
 A(m+1,0) 
 A(v,0) 
 A3 

 A(0,m+1) 
 A(0,v) 
 A(0,0) 
 A(0,1) 
 A(0,m) 
 A2 
 A(1,0) 
 A(m,0) 
 A1 

получим дважды диагональный латинский квадрат.

Аналогично с ортогональными квадратами. Если в дополнение к уже названным условиям взять по паре ортогональных квадратов V, Q, P1, получим пару ортогональных дважды диагональных латинских кваратов.

Для примера возьмем следующие квадраты (Квадрат P порядка 1):

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

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

 P1 
 3 
 4 
 2 
 2 
 3 
 4 
 4 
 2 
 3 


После выполнения операции получим такой квадрат:

   1   
 (3,1) (4,1) (2,1) 
 (3,2) (4,2) (2,2) 
 (3,3) (4,3) (2,3) 
 (3,4) (4,4) (2,4) 
 (4,1) 
 (2,1) 
 (3,1) 
 (2,1)   1   (3,1) 
 (4,1) (3,1)   1   
   1   (2,1) (4,1) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (4,2) 
 (2,2) 
 (3,2) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (2,2)   1   (3,2) 
 (4,2) (3,2)   1   
   1   (2,2) (4,2) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (4,3) 
 (2,3) 
 (3,3) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (2,3)   1   (3,3) 
 (4,3) (3,3)   1   
   1   (2,3) (4,3) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (4,4) 
 (2,4) 
 (3,4) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (2,4)   1   (3,4) 
 (4,4) (3,4)   1   
   1   (2,4) (4,4) 

Меняем местами части квадрата:

 (2,3)   1   (3,3) 
 (4,3) (3,3)   1   
   1   (2,3) (4,3) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (4,3) 
 (2,3) 
 (3,3) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (2,4)   1   (3,4) 
 (4,4) (3,4)   1   
   1   (2,4) (4,4) 
 (4,4) 
 (2,4) 
 (3,4) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (3,3) (4,3) (2,3) 
 (3,4) (4,4) (2,4) 
   1   
 (3,1) (4,1) (2,1) 
 (3,2) (4,2) (2,2) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (3,2) (4,2) (2,2) 
 (2,2) (3,2) (4,2) 
 (4,2) (2,2) (3,2) 
 (4,1) 
 (2,1) 
 (3,1) 
 (2,1)   1   (3,1) 
 (4,1) (3,1)   1   
   1   (2,1) (4,1) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (3,1) (4,1) (2,1) 
 (2,1) (3,1) (4,1) 
 (4,1) (2,1) (3,1) 
 (3,3) (4,3) (2,3) 
 (2,3) (3,3) (4,3) 
 (4,3) (2,3) (3,3) 
 (4,2) 
 (2,2) 
 (3,2) 
 (3,4) (4,4) (2,4) 
 (2,4) (3,4) (4,4) 
 (4,4) (2,4) (3,4) 
 (2,2)   1   (3,2) 
 (4,2) (3,2)   1   
   1   (2,2) (4,2) 

Заменяем пары чисел значениями от 0 до v(q-p)+p-1 :

DDLS(13)
  0 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
  6 
  2 
  1 
  5 
  3 
  4 
  0 
  9 
  7 
  8 
 12 
 10 
 11 
  1 
  0 
  6 
  4 
  5 
  3 
  2 
  8 
  9 
  7 
 11 
 12 
 10 
  7 
  8 
  9 
 12 
  1 
 10 
 11 
  2 
  6 
  0 
  3 
  4 
  5 
  9 
  7 
  8 
 11 
 10 
  1 
 12 
  0 
  2 
  6 
  5 
  3 
  4 
  8 
  9 
  7 
  1 
 12 
 11 
 10 
  6 
  0 
  2 
  4 
  5 
  3 
  2 
  6 
  0 
 10 
 11 
 12 
  1 
  3 
  4 
  5 
  7 
  8 
  9 
 10 
 11 
 12 
  7 
  8 
  9 
  4 
  5 
  1 
  3 
  2 
  6 
  0 
 12 
 10 
 11 
  9 
  7 
  8 
  5 
  4 
  3 
  1 
  0 
  2 
  6 
 11 
 12 
 10 
  8 
  9 
  7 
  3 
  1 
  5 
  4 
  6 
  0 
  2 
  3 
  4 
  5 
  2 
  6 
  0 
  8 
 10 
 11 
 12 
  9 
  1 
  7 
  5 
  3 
  4 
  0 
  2 
  6 
  9 
 12 
 10 
 11 
  8 
  7 
  1 
  4 
  5 
  3 
  6 
  0 
  2 
  7 
 11 
 12 
 10 
  1 
  9 
  8 

Дополнительные примеры можно получить воспользовавшись приложением.

1Charles C.Linder. Construction Of Doubly Diagonalized Orthogonal Latin Squares. 1972


В приложении исходники реализации метода и приложение для генерации дважды диагональных квадратов. В параметрах приложения указываются значения v p q. По заданным параметрам строятся необходимые квадраты V Q P1, для них выполняется описанная выше операция и выводится DDLS. На экран выводятся также все промежуточные результаты. Например: test 4 4 10

Генерация ортогональных диагональных квадратов не реализована.
Downloads
Исходники и приложение для получения DDLS (test_dols_2.zip) (34 Кб, просмотров: 1426 )

No comments
Вы можете оставить комментарий или задать вопрос
Ваше имя:

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


Copyright © 2009-2014 by