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

omega · Сообщение **omega** » 01 июн 2011, 10:38

Итак, для порядков 9, 16, 25, 49 построены совершенные латинские квадраты и для каждого найден ортогональный соквадрат, при этом ортогональные соквадраты тоже совершенные.

Совершенный квадрат 36-го порядка построен (см. пост #20), однако ортогональный соквадрат для этого квадрата найти пока не удалось.

Ещё одна хор-р-р-ошая задача!

Сейчас попробую ещё отражение относительно главной диагонали. Много чего уже перепробовала.
Пока всё безуспешно, не получается ортогональный квадрат

Ну, как тут можно решать?
Определение ортогональных латинских квадратов выше приведено.
Разумеется, тупой перебор отпадает. Нужно делать что-то осмысленное. Но это "что-то" надо придумать.

Хотя вполне может быть, что для этого латинского квадрата ортогональный соквадрат вообще не существует.
***
Попробовала отражение относительно обеих главных диагоналей, опять мимо.

omega · Сообщение **omega** » 02 июн 2011, 02:43

Вот опять меня задача зацепила

Как жаль, что только меня

Сегодня утром проснулась ещё с одной идеей: искать ортогональные блоки построчно.
Ну, не может быть, чтобы из огромадного количества вариантов перестановок строк не нашёлся ортогональный вариант! А может, и может В этой дьявольской комбинаторике всё возможно.

Итак, что я делаю? Беру первую строку исходного квадрата, она ортогональна самой себе. Далее беру 2 строки исходного квадрата, вторую строку искомого ортогонального квадрата варьирую, так нашла ортогональный блок из двух строк, ну и далее уже понятно.
Программу пока не писала, вручную варьировала строки. С ходу удалось найти пару ортогональных блоков из 6 строк.
Это 6 строк исходного квадрата:

Код: Выбрать все

0 5 4 3 2 1 35 31 34 33 32 30 28 29 26 27 24 25 23 20 22 21 18 19 14 17 12 15 16 13 7 6 10 9 8 11
11 7 10 9 8 6 1 5 4 3 2 0 30 32 34 33 35 31 24 29 27 28 25 26 18 21 23 22 19 20 12 14 13 15 17 16
16 17 14 15 12 13 6 8 10 9 11 7 2 5 4 3 0 1 30 33 34 35 31 32 24 29 28 27 26 25 18 21 19 23 22 20
20 23 22 21 18 19 12 17 15 16 13 14 6 9 10 11 7 8 3 5 4 0 2 1 30 34 35 31 32 33 24 28 29 26 27 25
26 29 24 27 28 25 18 23 20 19 21 22 12 17 16 15 14 13 6 10 11 7 8 9 4 5 0 3 2 1 30 35 31 33 32 34
31 30 34 33 32 35 24 26 25 27 29 28 18 23 22 20 21 19 12 16 17 14 15 13 6 11 7 9 8 10 5 0 4 3 2 1

Это 6 строк искомого ортогонального квадрата:

Код: Выбрать все

0 5 4 3 2 1 35 31 34 33 32 30 28 29 26 27 24 25 23 20 22 21 18 19 14 17 12 15 16 13 7 6 10 9 8 11 
16 17 14 15 12 13 6 8 10 9 11 7 2 5 4 3 0 1 30 33 34 35 31 32 24 29 28 27 26 25 18 21 19 23 22 20 
11 7 10 9 8 6 1 5 4 3 2 0 30 32 34 33 35 31 24 29 27 28 25 26 18 21 23 22 19 20 12 14 13 15 17 16 
31 30 34 33 32 35 24 26 25 27 29 28 18 23 22 20 21 19 12 16 17 14 15 13 6 11 7 9 8 10 5 0 4 3 2 1
6 11 7 10 9 8 0 1 5 4 3 2 31 30 32 34 33 35 26 24 29 27 28 25 20 23 18 21 22 19 16 12 14 13 15 17 
19 20 23 18 22 21 14 12 17 15 16 13 8 6 9 10 11 7 1 3 5 4 0 2 33 30 34 35 31 32 25 24 28 29 26 27

Если нигде не ошиблась, это ортогональные блоки.
До этого мне не удалось получить ни одной пары ортогональных блоков даже из 6 строк.

Это, конечно, почти то же самое, что и программа полной перестановки строк, которая, понятно, будет выполняться очень долго.
Но, может быть, в предложенном алгоритме повезёт быстрее, чем при полной перестановке строк.
Хотя на везение можно рассчитывать только в том случае, если ортогональный соквадрат для данного латинского квадрата 36-го порядка существует.

Опять же надо написать программу, реализующую предложенный алгоритм, хорошо её написать, с толком

omega · Сообщение **omega** » 02 июн 2011, 04:07

Прогнала вручную первый проход, удалось получить пару ортогональных блоков из 11 строк.
Из исходного квадрата не буду блок из 11 строк показывать, он уже в самом исходном квадрате показан.
А это ортогональный блок из 11 строк:

Код: Выбрать все

0 5 4 3 2 1 35 31 34 33 32 30 28 29 26 27 24 25 23 20 22 21 18 19 14 17 12 15 16 13 7 6 10 9 8 11 
16 17 14 15 12 13 6 8 10 9 11 7 2 5 4 3 0 1 30 33 34 35 31 32 24 29 28 27 26 25 18 21 19 23 22 20 
11 7 10 9 8 6 1 5 4 3 2 0 30 32 34 33 35 31 24 29 27 28 25 26 18 21 23 22 19 20 12 14 13 15 17 16 
31 30 34 33 32 35 24 26 25 27 29 28 18 23 22 20 21 19 12 16 17 14 15 13 6 11 7 9 8 10 5 0 4 3 2 1
6 11 7 10 9 8 0 1 5 4 3 2 31 30 32 34 33 35 26 24 29 27 28 25 20 23 18 21 22 19 16 12 14 13 15 17 
19 20 23 18 22 21 14 12 17 15 16 13 8 6 9 10 11 7 1 3 5 4 0 2 33 30 34 35 31 32 25 24 28 29 26 27 
3 2 1 0 5 4 33 32 30 35 31 34 27 24 25 28 29 26 18 21 19 20 23 22 15 16 13 14 17 12 9 8 11 7 6 10
27 28 25 26 29 24 19 22 21 18 20 23 15 14 13 12 17 16 7 8 9 6 10 11 3 2 1 4 5 0 33 32 34 30 35 31
10 9 8 6 11 7 4 3 2 0 1 5 34 33 35 31 30 32 27 28 25 26 24 29 21 19 22 20 18 23 13 15 17 16 12 14
34 33 32 35 31 30 25 27 29 28 24 26 22 19 21 23 18 20 17 14 15 13 12 16 7 9 8 10 6 11 4 3 2 1 5 0
14 15 12 13 16 17 10 9 11 7 6 8 4 3 0 1 2 5 34 35 31 32 30 33 28 27 26 25 24 29 22 23 18 20 19 21

Ну, вручную поигралась со строками (конечно, не совсем вручную, программу проверки ортогональности блоков использовала), теперь надо писать нормальную программу перестановки строк.

Так существует ли ортогональный соквадрат к приведённому совершенному латинскому квадрату 36-го порядка?

omega · Сообщение **omega** » 07 июн 2011, 03:23

Посетила сайт alexBlack.

Нашла построение пары ортогональных диагональных квадратов 12-го порядка:
[url=http://alexblack.wallst.ru/article.php?content=124]http://alexblack.wallst.ru/article.php?content=124[/url]
В статье автор ссылается на следующую работу:
Consolato Pellegrino and Paola Lancellotti. A New Construction Of Doubly Diagonal Orthogonal Latin Squares
Не знаю год написания статьи.

В некоторый момент времени в этой области оставались такие проблемные порядки: 10, 14, 15, 18, 26.
В 1982 г. в статье “ORTOGONAL DIAGONAL LATIN SQUARES OF ORDER FOURTEEN” (L. Zhu) решается вопрос для порядка 14. Очень оригинальный метод!
В 1989 г. А.В. Назарок пишет статью, в которой решает ещё три проблемы – для порядков 15, 18 и 26.
И, наконец, в 1992 г. в статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие) решается задача построения пар ОДЛК 10-го порядка.

ОДЛК порядков 15 и 18 я построила сама. Теперь у меня осталась одна неизвестная пара ОДЛК – 26-го порядка.

Ещё раз напомню, что статью:
А. В. Назарок. Пары ортогональных дважды диагональных латинских квадратов порядков 15, 18 и 26. // Комбинаторный анализ. Вып. 32. М.: МГУ, 1989 г. (предположительно стр. 154-168).
мне найти не удалось.

Я обращалась с просьбой помочь найти эту статью на многих форумах, в том числе и на данном. Но, увы!
Может быть, статья вообще не выложена в Сети? Такое возможно?
Сама потратила много часов на её поиски в Интернете. Заходила в электронные библиотеки по ссылкам, данным мне Дивелопером. В одной из библиотек увидела другую статью этого автора, но скачать её мне не дали почему-то. Там что-то с доступом в библиотеку что ли, так и не поняла толком.

И представьте: больше ни в каких источниках не нашла решение этой задачи. Возможно, есть в англоязычных статьях, но у меня плохо с поиском этих статей, так как не знаю английского.

По данной теме можно посмотреть мою статью:

[img]/modules/file/icons/application-octet-stream.png[/img] diagon.rar

Кстати, вот работа того же автора, которую я нашла в одной из электронных библиотек:
Назарок, Андрей Владимирович. Исследование ортогональных латинских квадратов и других комбинаторных конструкций:: автореферат диссертации кандидата физико-математических наук: 01.01.09/ Киев. гос. ун-т Киев, 1991, 11 стр.

Тоже с интересом посмотрела бы эту работу, но не удалось скачать.

Да, так вот задача:
построить пару ортогональных диагональных латинских квадратов 26-го порядка.

Назарок ведь построил, чем мы хуже?

omega · Сообщение **omega** » 07 июн 2011, 04:18

Просмотрела свою статью о ОДЛК.
Кроме проблемных порядков, указанных выше, я не знаю, как строить пары ОДЛК и для нескольких других порядков, например, 21, 24. Метод составных квадратов для этих порядков не работает.

Тогда решила проверить построение ОДЛК порядка 24 методом, описанным в статье alexBlack.
Как я поняла метод годится для порядков серии $$n = 3k$$

для чётных k.
Порядок 24 как раз входит в эту серию порядков.
Скачала программу с сайта alexBlack.
Взяла известную пару ОДЛК 8-го порядка и выполнила программу.
Мгновенно получила пару ОДЛК 24-го порядка. Класс!

Код: Выбрать все

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

alexBlack
здорово! Спасибо!

Но вот для порядка 21 этот метод не годится. Что-нибудь для этого порядка можно придумать? :rolleyes:
Как я поняла, и для указанной серии порядков он не всегда срабатывает.
Сейчас попробую для порядка 42.

Взяла пару ОДЛК 14-го порядка, построенную методом L. Zhu.
Запустила программу, выдалось сообщение:
transversal T1 not found in squares
Значит, для этого порядка не сработало.

Такой интересный вопрос: если взять другую пару ОДЛК 14-го порядка, можно получить иной результат?
А может, k должно быть не просто чётным, а чётно-чётным?

Попробовала построить пару ОДЛК 36-го порядка. Такая пара сразу построилась:

Код: Выбрать все

16 5 6 7 4 3 0 10 9 8 11 1 2 15 12 13 14 17 18 20 23 22 21 34 25 26 35 24 33 32 27 30 31 28 29 19 
 7 18 5 4 1 6 8 2 10 11 3 9 13 0 15 14 19 12 22 16 20 21 32 23 24 27 26 33 34 35 28 25 30 29 17 31 
 5 4 19 6 3 9 7 0 8 2 10 11 15 14 1 12 17 23 13 18 22 25 20 21 26 33 34 35 32 31 24 27 28 16 30 29 
 6 7 4 17 11 1 2 5 0 10 9 8 12 13 14 3 21 19 16 15 27 20 23 22 35 24 33 32 29 34 25 26 18 30 31 28 
 1 11 3 2 20 0 5 9 7 6 8 4 19 21 17 16 10 18 15 31 13 12 22 14 34 29 32 25 30 27 26 23 24 35 28 33 
 9 3 0 1 2 22 11 7 4 5 6 10 23 17 18 19 16 8 29 13 14 15 12 20 31 32 27 34 25 28 21 24 33 26 35 30 
 0 1 2 8 6 10 23 3 11 7 4 5 18 19 16 22 12 30 9 17 21 13 14 15 27 34 25 28 35 20 31 32 29 24 33 26 
 3 2 10 0 8 4 1 21 5 9 7 6 17 16 20 18 28 14 19 11 15 23 13 12 32 25 30 27 22 33 34 29 26 31 24 35 
11 10 9 5 0 7 4 8 12 1 2 3 21 20 23 26 18 13 14 22 6 19 16 17 29 30 31 15 27 24 33 28 35 34 25 32 
 8 9 7 11 5 2 10 6 3 14 1 0 22 23 24 21 15 16 20 12 17 4 19 18 28 31 13 29 26 25 30 35 32 33 34 27 
10 6 8 9 7 11 3 4 1 0 15 2 20 35 22 23 13 21 17 14 19 18 5 16 30 12 28 31 24 29 32 33 34 27 26 25 
 4 8 11 10 9 5 6 1 2 3 0 13 33 22 21 20 23 15 12 19 16 17 18 7 14 28 29 30 31 26 35 34 25 32 27 24 
12 27 13 16 15 19 14 23 22 21 20 17 28 18 7 25 26 29 30 32 35 34 33 31 8 0 24 2 5 11 10 3 6 1 4 9 
25 14 18 15 17 13 21 12 23 20 19 22 16 30 27 5 31 24 34 28 32 33 29 35 2 10 0 26 9 7 1 8 3 4 11 6 
18 15 17 13 19 35 16 14 21 12 23 20 27 26 31 24 29 22 25 30 34 28 3 33 0 5 9 7 11 6 2 10 1 8 32 4 
13 16 15 19 33 17 12 18 14 23 22 21 24 25 26 29 20 31 28 27 30 32 35 1 7 2 5 11 4 9 8 0 10 3 6 34 
17 20 29 12 23 14 18 22 16 13 21 15 31 33 19 28 32 10 27 35 25 24 34 26 9 4 11 8 3 30 0 6 2 7 1 5 
22 19 14 31 12 21 20 16 15 18 13 23 35 29 30 17 8 34 33 25 26 27 24 32 6 11 10 9 28 1 4 2 5 0 7 3 
14 17 12 21 13 23 22 19 20 16 26 18 30 31 28 34 24 32 35 29 33 2 15 27 10 9 8 1 7 3 6 11 4 25 5 0 
19 12 23 14 21 15 17 20 18 22 16 24 29 28 32 30 34 26 31 33 0 35 25 13 11 8 3 10 1 5 9 4 27 6 2 7 
20 23 22 18 14 16 15 34 13 17 12 19 4 32 35 27 30 25 26 21 24 31 28 29 33 3 6 0 10 2 5 1 7 9 8 11 
21 22 16 20 18 12 32 13 19 15 17 14 34 6 25 33 27 28 23 24 29 26 31 30 1 35 2 4 0 8 3 7 11 5 9 10 
23 13 21 22 16 20 19 15 17 30 18 12 32 24 34 35 25 33 11 26 31 14 27 28 3 7 1 6 2 4 29 5 9 10 0 8 
15 21 20 23 22 18 13 17 28 19 14 16 26 34 33 32 35 27 24 9 12 29 30 25 5 1 4 3 6 0 7 31 8 11 10 2 
30 31 27 29 25 26 28 35 34 33 32 7 14 3 0 1 2 5 6 8 11 10 9 24 4 17 18 19 16 15 12 22 21 20 23 13 
29 28 31 25 24 27 33 30 35 32 5 34 1 12 3 2 7 0 10 4 8 9 26 11 19 6 17 16 13 18 20 14 22 23 15 21 
31 25 24 27 26 34 29 28 33 4 35 32 3 2 13 0 5 11 1 6 10 30 8 9 17 16 7 18 15 21 19 12 20 14 22 23 
27 29 25 26 32 24 30 31 6 35 34 33 0 1 2 15 9 7 4 3 28 8 11 10 18 19 16 5 23 13 14 17 12 22 21 20 
24 32 26 30 35 28 31 11 29 27 33 25 7 9 5 4 22 6 3 34 1 0 10 2 13 23 15 14 8 12 17 21 19 18 20 16 
34 26 28 24 30 33 9 29 25 31 27 35 11 5 6 7 4 20 32 1 2 3 0 8 21 15 12 13 14 10 23 19 16 17 18 22 
28 24 30 33 27 8 34 26 32 29 25 31 6 7 4 10 0 35 21 5 9 1 2 3 12 13 14 20 18 22 11 15 23 19 16 17 
26 30 35 28 10 25 24 32 31 34 29 27 5 4 8 6 33 2 7 23 3 11 1 0 15 14 22 12 20 16 13 9 17 21 19 18 
32 35 34 3 28 29 25 33 27 24 30 26 9 8 11 31 6 1 2 10 18 7 4 5 23 22 21 17 12 19 16 20 0 13 14 15 
33 34 1 32 31 30 35 27 26 25 24 28 10 11 29 9 3 4 8 0 5 16 7 6 20 21 19 23 17 14 22 18 15 2 13 12 
35 0 33 34 29 32 26 25 24 28 31 30 8 27 10 11 1 9 5 2 7 6 17 4 22 18 20 21 19 23 15 16 13 12 3 14 
 2 33 32 35 34 31 27 24 30 26 28 29 25 10 9 8 11 3 0 7 4 5 6 19 16 20 23 22 21 17 18 13 14 15 12 1 
----
32 7 4 9 10 5 6 8 11 2 1 3 0 27 24 25 26 33 34 30 29 28 31 18 17 14 13 12 15 16 19 23 20 21 22 35 
 4 35 10 7 6 9 11 5 1 8 0 2 24 3 26 27 34 25 29 33 31 30 17 28 13 18 15 14 19 12 20 16 22 23 32 21 
 9 4 33 10 3 1 7 0 8 6 2 11 25 24 5 26 35 31 27 32 30 19 28 29 12 13 16 15 18 22 14 17 23 34 21 20 
 7 10 9 34 2 0 3 4 5 11 8 1 27 26 25 6 28 32 35 24 16 29 30 31 14 15 12 19 21 17 18 13 33 20 23 22 
 1 9 11 2 24 8 0 7 6 3 10 5 31 25 29 28 4 30 32 14 34 35 26 33 22 12 20 21 13 23 17 27 19 18 15 16 
10 2 1 8 11 27 4 3 0 5 6 9 26 28 31 30 29 7 13 35 32 33 34 25 15 21 22 23 20 14 24 18 17 16 19 12 
 2 11 8 4 5 10 25 1 7 0 3 6 28 29 30 24 33 15 9 31 27 32 35 34 21 20 23 13 16 26 12 22 14 17 18 19 
 8 1 7 11 9 6 2 26 3 4 5 0 30 31 27 29 12 34 28 10 35 24 33 32 23 22 14 20 25 19 21 15 18 13 16 17 
 5 0 3 1 7 11 8 6 28 10 9 4 33 32 35 22 27 29 30 34 2 26 25 24 16 17 18 31 14 20 23 19 21 15 12 13 
 3 6 2 0 8 4 5 11 9 31 7 10 35 34 21 32 30 24 33 29 25 1 27 26 18 19 28 17 23 13 16 20 12 22 14 15 
 6 8 0 5 1 3 10 2 4 9 29 7 34 23 32 33 31 35 26 28 24 25 11 27 19 30 17 16 22 18 15 21 13 12 20 14 
11 5 6 3 0 2 1 9 10 7 4 30 20 33 34 35 32 28 31 25 26 27 24 8 29 16 19 18 17 21 22 12 15 14 13 23 
23 3 17 22 21 12 15 19 16 13 14 20 8 18 28 1 2 9 10 6 5 4 7 11 34 31 0 27 24 29 30 26 25 32 35 33 
 0 20 21 18 15 22 16 12 14 19 23 13 17 11 2 31 10 1 5 9 7 6 8 4 28 33 24 3 30 27 25 29 35 26 34 32 
22 17 12 21 20 7 18 23 19 15 13 16 1 0 9 2 11 14 3 8 6 10 32 5 27 28 29 24 33 35 31 34 26 30 4 25 
18 21 22 15 4 23 20 17 12 16 19 14 3 2 1 10 13 8 11 0 9 5 6 35 31 24 27 30 32 34 33 28 29 25 26 7 
14 22 5 13 17 19 23 18 15 20 21 12 7 1 16 4 0 26 8 3 10 11 2 9 35 27 25 32 28 6 34 31 30 33 24 29 
21 13 14 6 16 18 17 20 23 12 15 22 2 4 7 19 25 3 0 11 8 9 10 1 24 32 35 26 5 31 28 33 34 29 30 27 
13 16 19 17 12 21 22 14 18 23 11 15 4 5 6 0 9 2 1 7 3 34 20 10 32 25 26 28 29 24 27 35 31 8 33 30 
19 14 18 16 22 15 13 21 20 17 12 8 6 7 3 5 1 10 4 2 33 0 9 23 26 35 31 25 27 30 32 24 11 28 29 34 
12 23 20 14 18 16 19 10 13 21 22 17 29 8 11 7 3 5 6 15 4 2 1 0 9 34 33 35 31 25 26 30 32 24 27 28 
20 15 13 23 19 17 9 16 22 14 18 21 11 30 4 8 6 0 12 5 1 7 3 2 33 10 32 34 26 28 29 25 27 35 31 24 
15 19 23 12 14 20 21 13 17 1 16 18 10 6 8 9 7 11 24 4 0 22 5 3 30 26 34 29 35 33 2 32 28 27 25 31 
16 12 15 20 23 13 14 22 2 18 17 19 5 9 10 11 8 4 7 27 21 3 0 6 25 29 30 33 34 32 35 1 24 31 28 26 
29 26 25 24 27 28 31 35 32 33 34 23 9 15 12 13 14 21 22 18 17 16 19 30 20 6 5 2 1 0 3 7 4 11 8 10 
25 30 27 26 31 24 32 28 34 35 20 33 12 10 14 15 22 13 17 21 19 18 29 16 5 23 1 6 3 2 4 0 8 7 9 11 
24 25 28 27 30 34 26 29 35 22 33 32 13 12 0 14 23 19 15 20 18 31 16 17 2 5 21 1 10 8 6 9 7 3 11 4 
26 27 24 31 33 29 30 25 21 32 35 34 15 14 13 3 16 20 23 12 28 17 18 19 6 1 2 22 11 9 10 5 0 4 7 8 
34 24 32 33 25 35 29 15 31 30 27 28 19 13 17 16 5 18 20 26 22 23 14 21 8 2 4 11 12 7 9 6 3 10 1 0 
27 33 34 35 32 26 12 30 29 28 31 24 14 16 19 18 17 6 25 23 20 21 22 13 1 11 8 7 4 15 5 10 9 0 3 2 
33 32 35 25 28 14 24 34 26 29 30 31 16 17 18 12 21 27 2 19 15 20 23 22 11 4 7 5 0 1 13 8 6 9 10 3 
35 34 26 32 13 31 33 27 30 25 28 29 18 19 15 17 24 22 16 1 23 12 21 20 7 8 6 4 2 3 11 14 10 5 0 9 
28 29 30 19 26 32 35 31 33 27 24 25 21 20 23 34 15 17 18 22 11 14 13 12 0 9 10 8 6 4 7 3 16 1 2 5 
30 31 16 29 35 25 28 32 24 34 26 27 23 22 33 20 18 12 21 17 13 8 15 14 10 3 11 9 7 5 0 4 2 19 6 1 
31 18 29 28 34 30 27 33 25 24 32 26 22 35 20 21 19 23 14 16 12 13 4 15 3 7 9 0 8 10 1 11 5 2 17 6 
17 28 31 30 29 33 34 24 27 26 25 35 32 21 22 23 20 16 19 13 14 15 12 7 4 0 3 10 9 11 8 2 1 6 5 18

Итак, нужен пример построения данным методом пары ОДЛК порядка $$n =3k$$

при k одинарной чётности, чтобы убедиться, что метод работает и для таких случаев.

omega · Сообщение **omega** » 07 июн 2011, 05:30

alexBlack
у меня непонятки

Взяла свою пару ОДЛК 18-го порядка:

Запускаю программу, она выдаёт:

error in line 0
Square A must be double diagonal latin square

Как я понимаю, какой-то из квадратов не является диагональным по мнению программы.
Посмотрела на оба квадрата, вроде в них всё в порядке - они оба диагональные (дважды диагональные, то есть по обеим диагоналям).

Что не так у меня?

Кажется, поняла, что не так: ЛК надо писать в традиционной форме, то есть с 0.
А у меня пара ОДЛК 18-го порядка заполнена числами от 1 до 18.
Сейчас исправлюсь.

Ура! Из моей пары ОДЛК 18-го порядка построилась пара ОДЛК 54-го порядка!

Теперь надо попробовать для порядка 42 другие пары ОДЛК 14-го порядка.

omega · Сообщение **omega** » 07 июн 2011, 09:19

Для порядка 30 тоже не получилась пара ОДЛК, та же ошибка выдалась, что и для порядка 42.

Пар ОДЛК порядка 10 известно три. Сейчас для остальных двух попробую построить.

Нет, не получилось ни из одной пары ОДЛК 10-го порядка. Во всех случаях одно и то же сообщение.
***
Новый эксперимент: беру построенную мной пару ОДЛК 22-го порядка, это будет пара ОДЛК 66-го порядка, если будет.
Программа почему-то надолго задумалась. Ищет трансверсаль?
Для порядка 54 пара выдалась через 2 секунды, а здесь что-то медленно идёт поиск. Может, зависла?

Пара ОДЛК 22-го порядка:

Код: Выбрать все

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

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

Ура, построила пару ОДЛК 66-го порядка!

Фи, какие плохие пары ОДЛК настроили иностранцы: из пары 14-го порядка не получилось, из пар 10-го порядка тоже не получилось.
А из моих пар 18-го и 22-го порядков всё получилось

Итак, ещё задачи:
построить пары ОДЛК порядков 21, 30, 42.

***
И ещё проверила одну свою пару ОДЛК - 20-го порядка. Эта пара у меня построена методом составных квадратов.
Запустила для неё программу, пара ОДЛК 60-го порядка выдалась мгновенно.

alexBlack · Сообщение **alexBlack** » 07 июн 2011, 16:08

Для метода C.Pellegrino and P.Lancellotti Оба исходных квадрата должны иметь две общие трансверсали - довольно сильное ограничение и в статье не указано условий существования таких квадратов, кроме последнего абзаца:

например. поскольку для каждого существует пара $\mathrm{DDOLS}(2^r)$ , удовлетворяющих условиям, мы можем для каждого построить пару $\mathrm{DDOLS}(3 \cdot 2^r)$

Еще один метод описан в статье Charles C.Linder. "Construction Of Doubly Diagonalized Orthogonal Latin Squares." 1972
(В ближайшее время описание и программу выложу на сайте). Но там, по-моему, еще более жесткие ограничения:

из трех квадратов:

- квадрат $$V$$

- дважды диагональный четного порядка $$v$$

- квадрат

- диагональный (с одной главной диагональю) порядка $$q$$

и левый верхний угол этого квадрата - дважды диагональный порядка $$p$$

(самый простой вариант взять $$p = 1$$

)
- квадрат $$P_1$$

- диагональный (с одной побочной диагональю) порядка $$(q-p)$$

строим дважды диагональный квадрат порядка $$v(q-p)+p$$

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

omega · Сообщение **omega** » 08 июн 2011, 03:46

alexBlack
с нетерпением буду ждать новую статью!

Выкладываю по вашей просьбе статью:
Heinrich K. and Hilton A. J. W. Doubly diagonal orthogonal Latin squares. // Discrete Math. Vol. 46. № 2. 1983.

[img]/modules/file/icons/application-octet-stream.png[/img] heinrichDDLS.rar

Может, ещё кому будет интересна эта статья, а её нет в свободном доступе.
Мне многие статьи присылала одна дама из Швеции (софорумница по форуму dxdy.ru). У неё фантастические возможности по добыванию литературы, она может достать практически любую англоязычную статью. А вот с русскоязычными плохо у неё. Может быть, это не у неё плохо, а у нас плохо! Не заботимся мы о продвижении результатов русских исследователей по миру.

Сейчас прикинула значения v, q, p, что-то никак не могу получить моих проблемных порядков: 21, 26, 30, 42.

omega · Сообщение **omega** » 08 июн 2011, 09:49

Выше прикреплена моя статья "Ортогональные диагональные квадраты".

Сейчас написала приложение к этой статье - "Построение пар ортогональных диагональных латинских квадратов порядка $$3k$$

".
Прикреплена ниже эта статья.

В статье приведены результаты, полученные по программе alexBlack.
Я проделала эксперименты для порядков 12 - 66 (с шагом 6, исключая порядок 18). Не получились пары ОДЛК порядков 30 и 42.

Итак, проблемные для меня на сегодня порядки: 21, 26, 30, 42. Порядки 21 и 26 не относятся к указанной серии порядков. Но я не знаю, как построить и эти пары ОДЛК. Пары ортогональных латинских квадратов этих порядков у меня есть, а вот пар ортогональных диагональных латинских квадратов нет. Нигде пока не видела такие пары.

К вопросу о терминологии. Я употребляю термин "диагональные латинские квадраты", имея в виду, что в обеих главных диагоналях ЛК числа различны. Это соответствует английскому термину "doubly diagonal". Считаю излишним говорить по-русски: дважды диагональные. ЛК, в котором только в одной главной диагонали числа различны, считается не диагональным, как и ЛК, в котором в обеих главных диагоналях имеются одинаковые числа.

[img]/modules/file/icons/application-octet-stream.png[/img] ddolk.rar

yourdomain.com