|
|
В статье Линдера[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 :
Обозначим операцию сингулярное прямое произведение (далее в тексте просто
произведение) как 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
побочная диагональ является трансверсалью. Поэтому переставив части следующим
образом:
получим дважды диагональный латинский квадрат.
Аналогично с ортогональными квадратами. Если в дополнение к уже названным
условиям взять по паре ортогональных квадратов 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
| |
|
| |
После выполнения операции получим такой квадрат:
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
| |
Дополнительные примеры можно получить воспользовавшись приложением.
1↑Charles C.Linder.
Construction Of Doubly Diagonalized Orthogonal Latin Squares. 1972
В приложении исходники реализации метода и приложение для генерации
дважды диагональных квадратов. В параметрах приложения указываются
значения v p q. По заданным параметрам строятся необходимые
квадраты V Q P1, для них выполняется описанная выше операция и
выводится DDLS. На экран выводятся также все промежуточные результаты.
Например: test 4 4 10
Генерация ортогональных диагональных квадратов не реализована.
|