Programming: theory and practice by alexBlack


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

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

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

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

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

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

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

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

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

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

Утилиты

Компоненты

Контакты












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


В статье Ли Жу[1] (надеюсь, по русски читается именно так) приведено 
построение ортогональных диагональных латинских квадратов 14-го порядка.
К сожалению автор не указывает откуда взялись начальные последовательности 
и переходит сразу к построению квадрата. Ниже описывается алгоритм 
поиска нужных последовательностей для квадратов четного порядка. 




Пусть нам нужно построить пару DDOLS четного порядка  n. Рассмотрим 
построение одного квадрата. Второй строится аналогично, но из других 
начальных последовательностей. 




В правый нижний угол квадратов помещаем пару DDOLS порядка  p=4 -  Q1a и 
 Q1b на множестве {n-p, n-p+1, … , n-1}. Ниже в примерах элементы 
этого множества обозначены латинскими буквами. Границами квадратов 
 Q1a и  Q1b каждый из квадратов делится на четыре части. 
Верхнюю строку и часть левого столбца квадрата заполняем специально 
подобранными элементами (ниже мы называем их исходными последовательностями):




 (a0,0, a0,1, … ,a0,n-p-1) на множестве {0,1, … ,n-1} 
 (a0,n-p, a0,n-p+1, … ,a0,n-1) на множестве {0,1, … ,n-p-1} 
 (an-p,0, an-p+1,0, … ,an-1,0) на множестве {0,1, … ,n-p-1} 












  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
 A
 B
 C
 D

  
  
  
  
  
  
  
  
  
  
 D
 C
 B
 A

  
  
  
  
  
  
  
  
  
  
 B
 A
 D
 C

  
  
  
  
  
  
  
  
  
  
 C
 D
 A
 B





Остальные элементы определяются следующими простыми правилами:






    
 
  •  Для (0 ≤ i,j ≤ 9) элементы вычисляются по формуле  aij = (ai-1,j-1 + 1) mod (n-p)
для значений {0, 1, … , n-p-1} и  aij = ai-1,j-1  для значений {n-p, n-p+1, … , n-1}. 

    • 
 
  •  Для (1 ≤ r ≤ 9, n-p ≤ j ≤ n-1) элементы вычиляются по формуле  arj = (a0j + r) mod (n-p)

    • 
 
  •  Для (1 ≤ r ≤ 9, n-p ≤ i ≤ n-1) элементы вычиляются по формуле  air = (ai0 + r) mod (n-p)



То есть исходная последовательность полностью определяет квадрат. Нам нужны 
две такие последовательности (для каждого из ортогональных квадратов), причем, 
обе последовательности должны удовлетворять следующим требованиям:






    
 
  •  из исходных последовательностей по приведенным выше правилам должны строиться 
латинские квадраты с одной главной диагональю.

    • 
 
  •  две последовательности должны давать два ортогональных квадрата 

    • 
 
  •  и еще одно требование - в квадратах должна быть общая трансверсаль для 
левой верхней части квадрата, симметричная относительно главной диагонали. 



Начнем с главной диагонали. Ее можно взять одинаковой для обеих квадратов. 
Трансверсаль первого квадрата также можно задать сразу, как показано на 
рисунке: 













 0
  
  
  
  
 1
  
  
  
  
  
  
  
  

  
 1
  
  
  
  
 2
  
  
  
  
  
  
  

  
  
 2
  
  
  
  
 3
  
  
  
  
  
  

  
  
  
 3
  
  
  
  
 4
  
  
  
  
  

  
  
  
  
 4
  
  
  
  
 5
  
  
  
  

 6
  
  
  
  
 5
  
  
  
  
  
  
  
  

  
 7
  
  
  
  
 6
  
  
  
  
  
  
  

  
  
 8
  
  
  
  
 7
  
  
  
  
  
  

  
  
  
 9
  
  
  
  
 8
  
  
  
  
  

  
  
  
  
 0
  
  
  
  
 9
  
  
  
  

  
  
  
  
  
  
  
  
  
  
 A
 B
 C
 D

  
  
  
  
  
  
  
  
  
  
 D
 C
 B
 A

  
  
  
  
  
  
  
  
  
  
 B
 A
 D
 C

  
  
  
  
  
  
  
  
  
  
 C
 D
 A
 B





Остальные элементы исходных последовательностей довольно легко находятся 
простым перебором с возвратами. 




В частности для  n=14 получены следующие две последовательности:













A:
0  D  C  B  A  1  9  8  2  4
3  5  6  7
2  7  8  9

B:
0  9  8  7  6  2  D  C  B  A
5  4  1  3
9  5  1  3





Построим на их основе два квадрата 14-го порядка:


























 0
 D
 C
 B
 A
 1
 9
 8
 2
 4
 3
 5
 6
 7

 5
 1
 D
 C
 B
 A
 2
 0
 9
 3
 4
 6
 7
 8

 4
 6
 2
 D
 C
 B
 A
 3
 1
 0
 5
 7
 8
 9

 1
 5
 7
 3
 D
 C
 B
 A
 4
 2
 6
 8
 9
 0

 3
 2
 6
 8
 4
 D
 C
 B
 A
 5
 7
 9
 0
 1

 6
 4
 3
 7
 9
 5
 D
 C
 B
 A
 8
 0
 1
 2

 A
 7
 5
 4
 8
 0
 6
 D
 C
 B
 9
 1
 2
 3

 B
 A
 8
 6
 5
 9
 1
 7
 D
 C
 0
 2
 3
 4

 C
 B
 A
 9
 7
 6
 0
 2
 8
 D
 1
 3
 4
 5

 D
 C
 B
 A
 0
 8
 7
 1
 3
 9
 2
 4
 5
 6

 2
 3
 4
 5
 6
 7
 8
 9
 0
 1
 A
 B
 C
 D

 7
 8
 9
 0
 1
 2
 3
 4
 5
 6
 D
 C
 B
 A

 8
 9
 0
 1
 2
 3
 4
 5
 6
 7
 B
 A
 D
 C

 9
 0
 1
 2
 3
 4
 5
 6
 7
 8
 C
 D
 A
 B















 0
 9
 8
 7
 6
 2
 D
 C
 B
 A
 5
 4
 1
 3

 A
 1
 0
 9
 8
 7
 3
 D
 C
 B
 6
 5
 2
 4

 B
 A
 2
 1
 0
 9
 8
 4
 D
 C
 7
 6
 3
 5

 C
 B
 A
 3
 2
 1
 0
 9
 5
 D
 8
 7
 4
 6

 D
 C
 B
 A
 4
 3
 2
 1
 0
 6
 9
 8
 5
 7

 7
 D
 C
 B
 A
 5
 4
 3
 2
 1
 0
 9
 6
 8

 2
 8
 D
 C
 B
 A
 6
 5
 4
 3
 1
 0
 7
 9

 4
 3
 9
 D
 C
 B
 A
 7
 6
 5
 2
 1
 8
 0

 6
 5
 4
 0
 D
 C
 B
 A
 8
 7
 3
 2
 9
 1

 8
 7
 6
 5
 1
 D
 C
 B
 A
 9
 4
 3
 0
 2

 9
 0
 1
 2
 3
 4
 5
 6
 7
 8
 A
 B
 C
 D

 5
 6
 7
 8
 9
 0
 1
 2
 3
 4
 C
 D
 A
 B

 1
 2
 3
 4
 5
 6
 7
 8
 9
 0
 D
 C
 B
 A

 3
 4
 5
 6
 7
 8
 9
 0
 1
 2
 B
 A
 D
 C







Элементы трансверсали, о которых мы говорили выше, вместе с побочной диагональю 
нижнего правого квадрата образуют трансверсаль для всего квадрата. Одновременной
заменой одинаковых строк и столбцов эту трансверсаль можно перевести в 
побочную диагональ квадрата (такая перестановка не разрушит главную диагональ). 
Таким образом мы получим:









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


















 0
 D
 C
 B
 A
 7
 6
 5
 3
 4
 2
 8
 9
 1

 5
 1
 D
 C
 B
 8
 7
 6
 4
 3
 9
 0
 2
 A

 4
 6
 2
 D
 C
 9
 8
 7
 5
 0
 1
 3
 A
 B

 1
 5
 7
 3
 D
 0
 9
 8
 6
 2
 4
 A
 B
 C

 3
 2
 6
 8
 4
 1
 0
 9
 7
 5
 A
 B
 C
 D

 9
 0
 1
 2
 3
 B
 A
 D
 C
 8
 7
 6
 5
 4

 8
 9
 0
 1
 2
 C
 D
 A
 B
 7
 6
 5
 4
 3

 7
 8
 9
 0
 1
 A
 B
 C
 D
 6
 5
 4
 3
 2

 2
 3
 4
 5
 6
 D
 C
 B
 A
 1
 0
 9
 8
 7

 D
 C
 B
 A
 0
 6
 5
 4
 2
 9
 3
 1
 7
 8

 C
 B
 A
 9
 7
 5
 4
 3
 1
 D
 8
 2
 0
 6

 B
 A
 8
 6
 5
 4
 3
 2
 0
 C
 D
 7
 1
 9

 A
 7
 5
 4
 8
 3
 2
 1
 9
 B
 C
 D
 6
 0

 6
 4
 3
 7
 9
 2
 1
 0
 8
 A
 B
 C
 D
 5















 0
 9
 8
 7
 6
 3
 1
 4
 5
 A
 B
 C
 D
 2

 A
 1
 0
 9
 8
 4
 2
 5
 6
 B
 C
 D
 3
 7

 B
 A
 2
 1
 0
 5
 3
 6
 7
 C
 D
 4
 8
 9

 C
 B
 A
 3
 2
 6
 4
 7
 8
 D
 5
 9
 0
 1

 D
 C
 B
 A
 4
 7
 5
 8
 9
 6
 0
 1
 2
 3

 3
 4
 5
 6
 7
 C
 D
 A
 B
 2
 1
 0
 9
 8

 1
 2
 3
 4
 5
 A
 B
 C
 D
 0
 9
 8
 7
 6

 5
 6
 7
 8
 9
 B
 A
 D
 C
 4
 3
 2
 1
 0

 9
 0
 1
 2
 3
 D
 C
 B
 A
 8
 7
 6
 5
 4

 8
 7
 6
 5
 1
 2
 0
 3
 4
 9
 A
 B
 C
 D

 6
 5
 4
 0
 D
 1
 9
 2
 3
 7
 8
 A
 B
 C

 4
 3
 9
 D
 C
 0
 8
 1
 2
 5
 6
 7
 A
 B

 2
 8
 D
 C
 B
 9
 7
 0
 1
 3
 4
 5
 6
 A

 7
 D
 C
 B
 A
 8
 6
 9
 0
 1
 2
 3
 4
 5







Получены последовательности для следущих порядков:













DDOLS(14)

A :
0  D  C  B  A  1  9  8  2  4
3  5  6  7
2  7  8  9

B :
0  9  8  7  6  2  D  C  B  A
5  4  1  3
9  5  1  3

DDOLS(16)

A :
0  D  C  B  A 11  1 10  9  6  2  4
3  5  7  8
2  8 10 11

B :
0 11  9  8 10  D  2  C  B  1  7  A
5  3  6  4
11  2  1  3

DDOLS(18)

A :
0  D  C  B  A 12 11  1 10 13  8  3  9  2
4  5  6  7
1  9 10 13

B :
0 13 12 11 10  D  C  2  B  8  A  1  3  6
9  7  5  4
11  1  3  2

DDOLS(20)

A :
0  D  C  B  A 15 14 13  1 12 11  9  3  8 10  4
2  5  6  7
2  4 13 15

B :
0 15 14 12 11  D  C  B  2  A  7  1 13  5  3 10
9  8  4  6
4 15  2  3

DDOLS(22)

A :
0  D  C  B  A 17 15 14 16  1 13  7 10 12 11  2  9  3
4  5  6  8
1  2  6 13

B :
0 17 16 15 14  D  C  B  A  2  9 13  7  3  5 12  4  6
11 10  8  1
5  1  4  3

DDOLS(24)

A :
0  D  C  B  A 19 18 17 16 15  1 14 10  9  3  8 13 12  2  6
4  5  7 11
1  2  5 19

B :
0 19 18 17 15  D  C  B  A 14  2 12  7 16 13  4  6  3 11  1
8 10  9  5
4  8 17  7

DDOLS(26)

A :
0  D  C  B  A 21 20 18 17 19 16  1 10 14  7 11 15  8 13  2  5  3
4  6  9 12
2  3  8 19

B :
0 21 20 19 18  D  C  B  A 17 15  2 13 10 16  5  4  1  3 12  9  8
11 14  6  7
4 17 21  3





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








1↑L.Zhu. Orthogonal Diagonal Latin Squares of order fourteen. 1982









Ниже приложение, которое позволяет сгенерировать последовательности и 
сформировать по ним латинские квадраты. При запуске нужно указать три параметра -
порядок квадратов, имя файла с DDOLS(4) (пример файла прилагается) и имя 
файла для вывода: test 16 DDOLK_4.txt 16.txt




Элементы  ≥ (n-p) выводятся в файл латинскими буквами. Если 
указать четвертый параметр (любой), латинские буквы будут заменены числами.



 

    
Downloads

      

        
        

    Приложение для получения DDOLS (test_dols_3.zip) (87.1 Кб, просмотров:  18257
)
        

        
      

   
 
 

    

      

      
Comments
          

      

            

      

      
      

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

         


           

                          Ваше имя: 

             

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

             

              
           


         

         
         

      
 
      


      
 
      

    






Copyright © 2009-2014 by