Латинские квадраты

[Nataly-Mak]

Нет, вы не поняли: типа "не читай мои труды".
Год-два назад у меня была другая позиция, а понимания, увы, так и не нашла нигде. Теперь позиция изменилась, потому что в мою бедную голову очень долго и нудно вдалбливали, что писать я не умею, что это никто не читает, что это никому не нужно, что это никто никогда не будет публиковать и т. д. и т. п. Если человеку всё время говорить, что он дурак, в конце концов он в это поверит.

[black cat]

пишу курсовую по ортогональным латинским квадратам, никому нигде не попадалась программа для их рассчета?

[Nataly-Mak]

В моих статьях есть несколько алгоритмов построения ортогональных латинских квадратов разных порядков. Алгоритмы несложно реализовать.

[black cat]

огромное спасибо

[maxal]

black cat в сообщении #298243 писал(а):

пишу курсовую по ортогональным латинским квадратам, никому нигде не попадалась программа для их рассчета?

В Maple и GAP'овском пакете GUAVA есть функция MOLS для построения ортогональных латинских квадратов.
См. http://www.gap-system.org/Manuals/pkg/g ... F2867080F7

[black cat]

мне нужно написать программу на basic или pascal, чтобы для введенного латинского квадрата она выдавала набор ему ортогональных.

[quasisuper]

Если вводимый латинский квадрат - произвольный, то такой программы не существует.
Построение всех латинских квадратов, ортогональных данному - это открытая (и трудная) теоретическая задача. На настоящий момент доказано лишь, что при $n>6$ для любого заданного латинского квадрата порядка $n$ можно построить еще хотя бы один, ему ортогональный.

[black cat]

подскажите, сколько трансверсалей у латинского квадрата порядка n?

[fab3rok]

Здравствуйте! Описал задачу в разделе Программирование, но никак не дождусь там ответа, вот решил-таки обратиться в данную тему, может кто поможет...
Задача тут: Построение латинских квадратов (С++)

Перенесено из "Магические квадраты".

[Nataly-Mak]

Что-то заглохла тема без меня

А вообще-то тема латинских квадратов, безусловно, живёт и будет жить. Только всё как-то мимо нас проходит.
Я давно не занималась ЛК. А тут недавно получила письмо. Автор письма пишет, что нашёл алгоритм построения ортогональных ЛК порядка n=6k+2, где k=2m.

Приглашала его здесь выложить свой алгоритм, он ответил, что не умеет писать на форумах.
Ну, пока вразумительного изложения алгоритма я не добилась, но получила от него два ЛК порядка 26; проверила их на ортогональность по своей программе. Да, они действительно ортогональные.
Жду продолжения Может быть, всё-таки получу вразумительное описание аогоритма.

В своё время я не смогла сама построить два ортогональных ЛК порядка 26. Позже нашла в книге группу из 4-х взаимно ортогональных ЛК данного порядка.
[см. http://www.natalimak1.narod.ru/mols26_38.htm]

[Nataly-Mak]

Вразумительное описание алгоритма я так и не получила...

Но вот два ЛК 26-го порядка автор мне прислал, как я уже сообщала. Это, в самом деле ортогональные ЛК.

Чтобы квадраты не остались только в моей почте, покажу их здесь:

4 3 2 19 17 16 15 5 13 12 26 25 18 24 23 22 21 20 14 11 10 1 9 8 7 6 
15 5 4 3 1 18 17 16 6 14 13 26 25 19 24 23 22 21 20 12 11 2 10 9 8 7 
20 16 6 5 4 2 19 18 17 7 15 14 26 25 1 24 23 22 21 13 12 3 11 10 9 8 
21 20 17 7 6 5 3 1 19 18 8 16 15 26 25 2 24 23 22 14 13 4 12 11 10 9
22 21 20 18 8 7 6 4 2 1 19 9 17 16 26 25 3 24 23 15 14 5 13 12 11 10
23 22 21 20 19 9 8 7 5 3 2 1 10 18 17 26 25 4 24 16 15 6 14 13 12 11
24 23 22 21 20 1 10 9 8 6 4 3 2 11 19 18 26 25 5 17 16 7 15 14 13 12
6 24 23 22 21 20 2 11 10 9 7 5 4 3 12 1 19 26 25 18 17 8 16 15 14 13
25 7 24 23 22 21 20 3 12 11 10 8 6 5 4 13 2 1 26 19 18 9 17 16 15 14
26 25 8 24 23 22 21 20 4 13 12 11 9 7 6 5 14 3 2 1 19 10 18 17 16 15
3 26 25 9 24 23 22 21 20 5 14 13 12 10 8 7 6 15 4 2 1 11 19 18 17 16 
5 4 26 25 10 24 23 22 21 20 6 15 14 13 11 9 8 7 16 3 2 12 1 19 18 17
17 6 5 26 25 11 24 23 22 21 20 7 16 15 14 12 10 9 8 4 3 13 2 1 19 18 
9 18 7 6 26 25 12 24 23 22 21 20 8 17 16 15 13 11 10 5 4 14 3 2 1 19
11 10 19 8 7 26 25 13 24 23 22 21 20 9 18 17 16 14 12 6 5 15 4 3 2 1
13 12 11 1 9 8 26 25 14 24 23 22 21 20 10 19 18 17 15 7 6 16 5 4 3 2 
16 14 13 12 2 10 9 26 25 15 24 23 22 21 20 11 1 19 18 8 7 17 6 5 4 3
19 17 15 14 13 3 11 10 26 25 16 24 23 22 21 20 12 2 1 9 8 18 7 6 5 4
2 1 18 16 15 14 4 12 11 26 25 17 24 23 22 21 20 13 3 10 9 19 8 7 6 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
18 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 26 20 21 22 23 24 25 
7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 25 26 20 21 22 23 24 
14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 10 11 12 13 24 25 26 20 21 22 23
12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 10 11 23 24 25 26 20 21 22
10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 22 23 24 25 26 20 21
8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 21 22 23 24 25 26 20

 

4 15 20 21 22 23 24 6 25 26 3 5 17 9 11 13 16 19 2 1 18 7 14 12 10 8 
3 5 16 20 21 22 23 24 7 25 26 4 6 18 10 12 14 17 1 2 19 8 15 13 11 9 
2 4 6 17 20 21 22 23 24 8 25 26 5 7 19 11 13 15 18 3 1 9 16 14 12 10
19 3 5 7 18 20 21 22 23 24 9 25 26 6 8 1 12 14 16 4 2 10 17 15 13 11
17 1 4 6 8 19 20 21 22 23 24 10 25 26 7 9 2 13 15 5 3 11 18 16 14 12
16 18 2 5 7 9 1 20 21 22 23 24 11 25 26 8 10 3 14 6 4 12 19 17 15 13
15 17 19 3 6 8 10 2 20 21 22 23 24 12 25 26 9 11 4 7 5 13 1 18 16 14
5 16 18 1 4 7 9 11 3 20 21 22 23 24 13 25 26 10 12 8 6 14 2 19 17 15
13 6 17 19 2 5 8 10 12 4 20 21 22 23 24 14 25 26 11 9 7 15 3 1 18 16
12 14 7 18 1 3 6 9 11 13 5 20 21 22 23 24 15 25 26 10 8 16 4 2 19 17
26 13 15 8 19 2 4 7 10 12 14 6 20 21 22 23 24 16 25 11 9 17 5 3 1 18
25 26 14 16 9 1 3 5 8 11 13 15 7 20 21 22 23 24 17 12 10 18 6 4 2 19
18 25 26 15 17 10 2 4 6 9 12 14 16 8 20 21 22 23 24 13 11 19 7 5 3 1
24 19 25 26 16 18 11 3 5 7 10 13 15 17 9 20 21 22 23 14 12 1 8 6 4 2
23 24 1 25 26 17 19 12 4 6 8 11 14 16 18 10 20 21 22 15 13 2 9 7 5 3
22 23 24 2 25 26 18 1 13 5 7 9 12 15 17 19 11 20 21 16 14 3 10 8 6 4
21 22 23 24 3 25 26 19 2 14 6 8 10 13 16 18 1 12 20 17 15 4 11 9 7 5
20 21 22 23 24 4 25 26 1 3 15 7 9 11 14 17 19 2 13 18 16 5 12 10 8 6
14 20 21 22 23 24 5 25 26 2 4 16 8 10 12 15 18 1 3 19 17 6 13 11 9 7 
11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 10 26 25 24 23 22 21 20
10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 25 24 23 22 21 20 26
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 24 23 22 21 20 26 25
9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 23 22 21 20 26 25 24
8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 22 21 20 26 25 24 23
7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 21 20 26 25 24 23 22
6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 20 26 25 24 23 22 21

Может быть, кто-то сможет разобраться в схеме построения этих ортогональных ЛК.
Я пока не смогла.
Хотя очень старалась понять, что пишет автор, но получила, например, такое описание:

(Оффтоп)

Цитата:

Схема такая.Например,искомый порядок 38.Любой искомый порядок из серии 6n+2,где n=2k, можно разложить на 2 слагаемых.26= 19+7, 38=27+11, 86=59+27, A=6n+2=A+(A-5)/2 38=27+11, поэтому первоначальный ряд имеет 27 чисел.Шаг определяется по формуле A=(A+1)/2 (27+1)/2=14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 1 15 2 16 3 17 4 18 5 19 6 20 7 21 / 8 22 9 23 10 24 11 25 12 26 13 27 14 1 остается на месте. Числа соответствующие порядковым номерам с 15 по 27 меняются местами с числами соответствующим со 2 по 14 1 8 22 9 23 10 24 11 25 12 26 13 27 14 / 15 2 16 3 17 4 18 5 19 6 20 7 21 Теперь в новом ряду делается перестановка.Число под 14 порядковым номером меняется местом с 7, соответственно число под 15 номером с числом под 22 номером.Получается новый ряд. 1 8 22 9 23 10 14 11 25 12 26 13 27 24 / 5 2 16 3 17 4 18 15 19 6 20 7 21 Далее строится первоначальная верхняя строка 2 латинского квадрата.Тоже пока состоящая только из 27 чисел.Справа налево пишется натуральный ряд от 0 до 26. 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Суммируются 2 числа,стоящие под каждым порядковым номером.1+26, 8+25,22+24 и т.д.Если сумма больше 27, 27из суммы вычитается. Пишется справа налево.Последнее остается на месте,сумма под1порядковым номером переносится на предпоследнее место, соответственно предпоследняя сумма на 1место.Получается такой ряд 8 22 9 23 20 24 11 25 12 26 13 17 10 14 1 15 2 16 3 7 4 18 5 19 6 27 21 Теперь замена.Берем 1 ряд Последнее число переносится на первое место 21 1 8 22 9 23 10 14 11 25 12 26 13 27 24 5 2 16 3 17 4 18 15 19 6 20 7 38 37 36 35 34 33 32 31 30 29 28Пропуск ,который есть, легко определяется,для 38 порядка от середины 3 ячейка, для 26 2,для 50 4 и т.д.Меняются местами 38 на 5,37 на2, и т.д,Замененные числа переносятся дальше.Получается верхняя строка 1 латинского квадрата 21 1 8 22 9 23 10 14 11 25 12 26 13 27 24 38 37 16 36 35 34 33 32 31 30 29 28 /// 5 2 3 17 4 18 15 19 6 20 7 Верхняя строка 2 латинского квадрата.Последнее число на 1 место. 21 8 22 9 23 20 24 11 25 12 26 13 17 10 14 1 15 2 16 3 7 4 18 5 19 6 27 28 29 30 31 32 33 34 35 36 37 38 Также переписывается. 21 28 29 30 31 32 33 34 35 36 26 37 38 10 14 1 15 2 16 3 7 4 18 5 19 6 27 /// 8 22 9 23 20 24 11 25 12 13 17Далее строятся по известным правилам 2 латинских квадрата.
Если ляпов нет,они будут ортогональны

Может быть, кто-то сможет понять, что это за схема, и как по этой схеме составить, скажем, два ортгональных ЛК 38-го порядка, о чём в письме и пишется.

Автор - Андрей Саускан - сообщил, что построил по своей схеме и ортогональные ЛК 86-го порядка.
Он просил меня написать программу по его алгоритму и проверить ортогональные ЛК следующих порядков данной серии.
Но, увы, я не могу написать программу, пока не пойму схему составления квадратов.

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

[super.irinka]

Как построить пару дважды диагональных ортогональных латинских квадратов порядка 38?

[Pavlovsky]

Если Nataly-Mak не возражает озвучу смежную проблему.

Для заданного N, найти (N-2) ортогональных латинских прямоугольника размером Nx(N-1), заполненных числами [1,N].

[yk2ru]

Попытка расшифровки схемы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ( 26 = 19 +7 )
1 11 2 12 3 13 4 14 5 15 / 6 16 7 17 8 18 9 19 10 ( шаг 10 - [19+1]/2 )
1 6 16 7 17 8 18 9 19 10 / 11 2 12 3 13 4 14 5 15 ( замена позиций 2-10 с 11-19)
1 6 16 7 10 8 18 9 19 17 4 2 12 3 13 11 14 5 15 ( замена позиций 10 с 5 и 11 с 16)
( по тексту - для 2 квадрата:
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ( 0-18 наоборот )
19 4 13 3 5 2 11 1 10 7 12 9 18 8 17 14 16 6 15 ( сумма 2-х последних рядов и -19, если больше 19)
6 16 14 17 8 18 9 12 7 10 1 11 2 5 3 13 4 19 15 ( инверсия позиций 1-18)
)
15 1 6 16 7 10 8 18 9 19 17 4 2 12 3 13 11 14 5 26 25 24 23 22 21 20 ( 4 ряд с переносом последнего числа в начало и дополнением до 26 чисел)
15 1 6 16 7 10 8 18 9 19 17 26 2 25 24 23 22 21 20 /// 4 12 3 13 11 14 5 ( замена позиций 12-19 с 20-26 с пропуском 13 позиции)
И должна получиться 1-я строка латинского квадрата, как утверждается.

[Nataly-Mak]

yk2ru в сообщении #593285 писал(а):

Попытка расшифровки схемы...

Очень мудрёно. Это можно формализовать, чтобы написать программу построения пары ОЛК, скажем, порядка 86?

Кстати, сам автор схемы здесь, это пользователь super.irinka.
Он может сказать, правильно ли вы расшифровали схему