Programming: theory and practice by alexBlack


Главная Эксперименты Утилиты Компоненты Что почитать Контакты
Главная
Эксперименты 
 Латинские квадраты

Диагональные латинские квадраты

Совершенные латинские квадраты

ОДЛК. Метод Пелегрино-Ланселотти

ОДЛК. Метод Линдера

ОДЛК. Метод Ли Жу

 Магические квадраты

9x9. Пандиагональные

9x9. Идеальные из простых чисел

6x6. Пандиагональные

Утилиты

Компоненты

Контакты












ОДЛК. Метод Пелегрино-Ланселотти


В статье Пелегрино и Ланселотти[1] приводится доказательство существования пары ортогональных 
диагональных латинских квадратов для некоторых значений  n=3k. 




Если кратко, то, по двум ортогональным диагональным латинским квадратам 
четного порядка  k  ( DDOLS(k)) можно построить пару  DDOLS(3k).




Здесь мы рассмотрим метод построения таких квадратов, описанный в статье. 
Возьмем, например, пару  DDOLS(4) - квадраты  A  и  B :

























 0 
 1 
 2 
 3 

 3 
 2 
 1 
 0 

 1 
 0 
 3 
 2 

 2 
 3 
 0 
 1 















 0 
 1 
 2 
 3 

 2 
 3 
 0 
 1 

 3 
 2 
 1 
 0 

 1 
 0 
 3 
 2 







Эти два квадрата должны удовлетворять единственному требованию: 
для каждого из них должны иметься две общие для квадратов трансверсали 
(обозначим их  T1  и  T2 ), и эти трансверсали не должны иметь 
общих элементов между собой и с диагоналями квадратов. 
Диагонали квадратов обозначим  D1  (главная) и  D2  (побочная). 
Для выбранных нами квадратов нужные трансверсали выделены цветом.
(определение трансверсали в описании метода Гергели). 









comment



Это требование исключает нечетные значения  k .




Для латинского квадрата  Q  обозначим  Qh  копию квадрата  Q , 
полученную увеличением каждого элемента квадрата на  h*k .









comment



В статье предлагается делать замену элемента  s  на пару (h, s), 
но сути это не меняет.




Получим два ортогональных квадрата порядка  3k :

























 A0
 A1
 A2

 A1
 A2
 A0

 A2
 A0
 A1















 B0
 B2
 B1

 B1
 B0
 B2

 B2
 B1
 B0







Для наших двух квадратов  A  и  B  получим следующие квадраты

























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

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

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















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

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

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







Далее введем обозначения. Для латинского квадрата  Q  сформируем 
перестановку  σS,T  на множестве  In  (символов этого квадрата)
следующим образом: элемент  In , занимающий ячейку  (h,i)  
трансверсали  S , ассоциируем с элементом  In , занимающий 
ячейку  (k,i)  трансверсали  T  (т.е ячейка  T  находится 
в той-же колонке). Обозначим  Q(S,T)  латинский квадрат, полученный 
заменой каждого элемента  s  квадрата  Q  
перестановкой  σS,T . 
(Такая перестановка, как показано в статье, оставляет на месте трансверсали 
и не нарушает ортогональность квадратов). 




Используя перестановки, сформированные для трансверсалей, из полученных
квадратов формируем другие два квадрата:

























 A11 = A0(D1,D2) 
 A12 = A1 
 A13 = A2(D2,T2) 

 A21 = A1(T1,D1) 
 A22 = A2 
 A23 = A0(T2,D1) 

 A31 = A2(D2,T1) 
 A32 = A0 
 A33 = A1(D1,D2) 















 B11 = B0(D1,T1) 
 B12 = B2 
 B13 = B1(D2,D1) 

 B21 = B1(T1,D2) 
 B22 = B0 
 B23 = B2(T2,D2) 

 B31 = B2(D2,D1) 
 B32 = B1 
 B33 = B0(D1,T2) 












comment



Судя по всему в статье здесь опечатка. Элемент  A31  должен формироваться 
из квадрата  A2 , а не из  A1 , как указано в статье.




Для нашего примера получим такие два квадрата:

























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

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

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















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

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

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







В этих двух квадратах:




множество элементов  Hj (j=1,2, … k)   j-й колонки 
левого квадрата, расположенных на трансверсалях  D1  квадрата  A11 , 
 T1  квадрата  A21  и  D2  квадарата  A31  совпадает с 
множеством  Hj"  элементов колонки  (k+j) , расположенных 
на трансверсалях  D1  квадрата  A12 ,  T1  квадрата  A22  
и  D2  квадрата  A32 . (эти два множества выделены в примере выше 
желтым цветом)




множество элементов  Kj  колонки  (k+j)
левого квадрата, расположенных на трансверсалях  D2  квадрата  A12 , 
 T2  квадрата  A22  и  D1  квадарата  A32  совпадает с 
множеством  Kj"  элементов колонки  (2k+j) , расположенных 
на трансверсалях  D2  квадрата  A13 ,  T2  квадрата  A23  
и  D1  квадрата  A33 .




Для каждого  j=1,2, … k  в левом квадрате меняем элементы  Hj  и 
 Hj" , расположенные в одной строке. Аналогично меняем элементы  Kj  и 
 Kj" , также из одной строки. 




Такие же замены делаем для правого квадрата. 




Получаем два ортогональных диагональных квадрата порядка  3k. 









DDOLS(12) / Пара ортогональных диагональных квадратов 12-го порядка


















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

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

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

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

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

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

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

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

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

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

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

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















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

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

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

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

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

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

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

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

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

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

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

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







Эти два квадрата также имеют по две трансверсали, удовлетворяющие условиям 
(на рисунке показаны серым цветом в разных квадратах) и по ним можно построить 
ортогональные диагональные квадраты 36-го порядка.








1↑Consolato Pellegrino and Paola Lancellotti. 
A New Construction Of Doubly Diagonal Orthogonal Latin Squares. 









В приложении исходники описанного алгоритма и приложение
для построения DDOLS. Два исходных квадрата должны быть записаны в текстовый 
файл (формат файла по аналогии с примером DDOLK_4.txt). При запуске в 
параметрах указываем имя файла с исходными квадратами. Если возможно, будут 
построены два диагональных ортогональных латинских квадрата. (Порядок 
исходных квадратов должен быть четный. Построение невозможно, если не 
будет найдено нужных трансверсалей.) 


 

    
Downloads

      

        
        

    Исходники и приложение (Windows/Delphi) для получения DDOLS (test_DDOLS.zip) (35 Кб, просмотров:  18324
)
        

        
      

   
 
 

    

      

      
Comments
          

      

      
09.06.2011 01:34  alexBlack  
 Извините, Наталия, случайно удалил Ваш комментарий пока редактировал ссылку. 
 Пары ОДЛК можно посмотреть здесь:
 Н.Макарова. Построение пар ортогональных диагональных латинских квадратов порядка 3k
 

28.06.2012 05:02  super.irinka 55555@yan  
 Здравствуйте,Алексей.Существуют-ли схемы построения дважды диагональных ортогональных 
 латинских квадратов любых порядков без применения компьютерных программ? Могу построить дважды 
 диагональные ортогональные латинские квадраты порядка 38,62,86. Полного алгоритма 
 пока нет. Поэтому интересуюсь. Андрей
 

      

      

      
      

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

         


           

                          Ваше имя: 

             

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

             

              
           


         

         
         

      
 
      


      
 
      

    






Copyright © 2009-2014 by