Как иногда полезно отвлечься от компьютера и посидеть в тишине!
Зашел как то в гости друг, на работе, говорит, прохожу реабилитацию, редкой минеральной водой поят, Зайечицкая горькая, попробуй, а то я минералку не люблю и в таких количествах не попиваю, остается... Вода дорогая, но полезная... Потому и дорогая, что полезная, практически как коньяк по Евгению Леонову. Посидели, друг ушел, вода осталась.
А на следующий день статью писать с коллегами про оптимизацию и распараллеливание канонизатора, они свою часть уже сделали, осталась моя с математикой выполняемых парастрофических преобразований и диагонализации и соответствующими алгоритмами.
Вода, мягко говоря, специфическая: мало того, что не газированная, так и еще и по вкусу левомецетин с небольшим количеством соды и капелькой йода. Опрокинул стакан залпом (организм, прими как лекарство), собрался с мыслями, начал писать. Прошло пару часов, мысли в голову так и лезут, но что-то живот начало подкручивать. И чем ближе к сути парастрофических преобразований, тем, как назло, все сильнее и сильнее (влияние парастрофических преобразований на биологические объекты не исследовано, надо будет заняться в перспективе :). Парастрофические преобразования, несмотря на страшное название, выполняются путем перестановки строк в ортогональном массиве размером 3 x N^2, где первая строка отвечает за номера строк элементов латинского квадрата, вторая — за номера столбцов, а третья — за стоящие в ячейках значения. Еще бы и картинку нарисовать к этому, но нет, сперва все же следует посетить уединенное заведение, а уже потом — картинки и все остальное, уж больно хорошо живот крутит. Что ж такое, то ли съел что-то не то... Чай с мятой — ел, бутеры — ел, вроде все как всегда...
В заведении хорошо, прохладно, тихо, никто не мешает, только компьютера не хватает: я тут, верхом, а писанина то — она там осталась... Ну да ладно, пользуясь моментом, отложим ее пока в сторону на полчасика и обдумаем одну интересную мысль... А нельзя ли обобщить классический ортогональный массив размера 3 x N^2? 3 x N^2 — это ЛК. А 4 x N^2 — это же пара ОЛК!!! И в нем тоже можно переставлять строки, т.е. фактически сделать обобщение парастрофических преобразований! А 5 x N^2? А это тройка MOLS. Ну и т.д. Как иногда полезно отвлечься от компьютера и посидеть в тишине!
Когда творческий позыв наконец пришел в норму, вернулся к компьютеру, статью отложил и начал обдумывать пришедшую идею. Закодил, проверил, оказалось, что в голове все сложилось правильно, работает!
PS. Ну а к вечеру, когда творческий эффект проявился не только у меня, но и у других членов семьи, решили на семейном совете почитать этикетку, интересно же, какие катионы и анионы дают такой горький вкус. В Абхазии помнится из источника сероводородную воду пили, жарко было, но до этой ей далеко... Оказалось, что эта минеральная вода обладает...
природным слабительным эффектом и рекомендуется при запорах! Скажи мне, кто твои друзья, и я скажу тебе, кто ты! Не один я подшучиваю, иногда и самому достается в отместку. Одну бутылочку я уработал, еще одна осталась, на работу с собой возьму в пятницу, коллег угощу... Они наверное такую страшно полезную и не пробовали, а в творческом порыве можно, например, серьезно продвинуть стратегические показатели кафедры, а то вечно мы что-то где-то недовыполняем...
Теперь по существу. Итак, очень простым преобразованием (обобщение известных парастрофических) можно из имеющейся пары ОЛК получить еще одну неизоморфную ей пару ОЛК, что позволяет удвоить имеющуюся коллекцию КФ ОДЛК. Точнее, удвоить можно ОЛК, с ОДЛК сложнее: для них удвоения не будет, но найденные ЛК в составе ОЛК можно скормить канонизатору, что иногда дает КФ ОДЛК. Из 4!=24 возможных комбинаций интерес представляет одна, в которой значения кортежа [x, y, v1, v2] изменяются на [v1, v2, x, y]. Остальные преобразования можно получить комбинацией данного с известными парастрофическими. Пример: возьмем 1-КФный цикл-4 и одну из пар ОДЛК в его составе
0 1 2 3 4 5 6 7 8 9
1 2 0 6 7 9 8 3 4 5
3 6 7 9 8 4 2 5 1 0
4 0 8 5 2 3 7 1 9 6
5 9 4 8 3 6 0 2 7 1
7 8 6 4 0 1 3 9 5 2
6 4 5 2 1 7 9 0 3 8
9 5 1 7 6 0 4 8 2 3
2 3 9 0 5 8 1 4 6 7
8 7 3 1 9 2 5 6 0 4
1 2 0 3 4 8 5 6 9 7
8 3 9 7 1 6 2 4 0 5
2 8 7 0 5 3 6 9 1 4
7 5 6 4 2 9 8 0 3 1
6 4 8 1 0 2 3 7 5 9
3 0 4 9 6 5 7 1 2 8
0 6 1 5 7 4 9 2 8 3
5 7 3 2 9 0 1 8 4 6
9 1 2 8 3 7 4 5 6 0
4 9 5 6 8 1 0 3 7 2
Применим к ней новое преобразование, в результате чего получается следующая пара ОЛК:
7 0 6 4 2 3 5 9 8 1
3 2 0 7 8 5 9 6 1 4
0 9 3 1 7 6 2 4 5 8
4 8 2 0 1 9 7 5 6 3
1 7 9 2 0 8 6 3 4 5
9 6 5 8 3 1 4 7 0 2
6 3 4 9 5 0 8 1 2 7
8 1 7 5 6 4 0 2 3 9
5 4 1 6 9 2 3 8 7 0
2 5 8 3 4 7 1 0 9 6
5 0 7 6 9 1 4 8 3 2
7 8 1 2 6 5 3 4 0 9
2 5 4 1 8 3 6 7 9 0
4 1 0 3 7 2 9 6 8 5
8 6 9 5 4 7 1 0 2 3
6 2 8 4 3 9 0 1 5 7
0 9 5 7 2 6 8 3 1 4
9 4 3 0 5 8 7 2 6 1
1 3 6 9 0 4 2 5 7 8
3 7 2 8 1 0 5 9 4 6
ЛК в ее составе ортогональны друг другу, но ДЛК не являются. Чтобы сделать из них ДЛК, применим к ним процедуру канонизации (поиска подходящих трансверсалей в их составе, диагонализации, т.е. установки этих трансверсалей на главную и побочную диагонали и проверки полученного ДЛК на наличие ОДЛК). В результате для первого квадрата получается следующее множество ДЛК, имеющих ОДЛК:
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 9 8 5 7
3 6 4 7 5 1 2 0 9 8
8 0 1 5 9 3 7 2 4 6
6 7 9 8 1 2 3 5 0 4
9 3 8 0 6 7 5 4 1 2
2 9 7 1 0 4 8 6 3 5
5 4 3 6 7 8 1 9 2 0
7 8 5 9 2 0 4 3 6 1
4 5 6 2 8 9 0 1 7 3
0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 9 7 5 3 6
3 5 8 0 7 6 4 1 9 2
4 7 3 6 5 8 0 9 2 1
5 0 9 8 1 7 2 4 6 3
8 9 1 7 2 4 3 6 5 0
2 4 6 5 3 0 9 8 1 7
7 6 4 1 9 2 5 3 0 8
9 8 5 2 6 3 1 0 7 4
6 3 7 9 0 1 8 2 4 5
0 1 2 3 4 5 6 7 8 9
1 2 3 0 5 7 8 9 6 4
7 8 4 1 6 3 9 0 2 5
2 5 6 9 1 0 7 8 4 3
8 9 0 4 7 2 3 5 1 6
4 0 9 6 3 8 2 1 5 7
3 6 7 8 0 1 5 4 9 2
9 3 1 5 2 4 0 6 7 8
6 4 5 7 8 9 1 2 3 0
5 7 8 2 9 6 4 3 0 1
0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 8 9 3 6 7
6 4 7 9 2 1 5 8 3 0
7 5 9 1 3 2 0 6 4 8
3 9 8 7 6 4 1 0 5 2
9 0 5 8 7 3 4 1 2 6
4 7 3 5 9 6 8 2 0 1
5 6 1 0 8 9 2 4 7 3
8 3 6 2 1 0 7 5 9 4
2 8 4 6 0 7 3 9 1 5
Для второго, соответственно:
0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 9 7 5 3 6
3 5 8 0 7 6 4 1 9 2
4 7 3 6 5 8 0 9 2 1
5 0 9 8 1 7 2 4 6 3
8 9 1 7 2 4 3 6 5 0
2 4 6 5 3 0 9 8 1 7
7 6 4 1 9 2 5 3 0 8
9 8 5 2 6 3 1 0 7 4
6 3 7 9 0 1 8 2 4 5
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 9 8 5 7
3 6 4 7 5 1 2 0 9 8
8 0 1 5 9 3 7 2 4 6
6 7 9 8 1 2 3 5 0 4
9 3 8 0 6 7 5 4 1 2
2 9 7 1 0 4 8 6 3 5
5 4 3 6 7 8 1 9 2 0
7 8 5 9 2 0 4 3 6 1
4 5 6 2 8 9 0 1 7 3
0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 8 9 3 6 7
6 4 7 9 2 1 5 8 3 0
7 5 9 1 3 2 0 6 4 8
3 9 8 7 6 4 1 0 5 2
9 0 5 8 7 3 4 1 2 6
4 7 3 5 9 6 8 2 0 1
5 6 1 0 8 9 2 4 7 3
8 3 6 2 1 0 7 5 9 4
2 8 4 6 0 7 3 9 1 5
0 1 2 3 4 5 6 7 8 9
1 2 3 0 5 7 8 9 6 4
7 8 4 1 6 3 9 0 2 5
2 5 6 9 1 0 7 8 4 3
8 9 0 4 7 2 3 5 1 6
4 0 9 6 3 8 2 1 5 7
3 6 7 8 0 1 5 4 9 2
9 3 1 5 2 4 0 6 7 8
6 4 5 7 8 9 1 2 3 0
5 7 8 2 9 6 4 3 0 1
Среди найденных 8 ДЛК с ОДЛК 2 пары 2-КФных однушек, т.е. 4 новые КФ ОДЛК. Затраты вычислительного времени — несколько секунд на выполнение канонизации (само преобразование выполняется мгновенно), что существенно быстрее, чем поиск КФ ОДЛК в проекте, где "стоимость" получения одной КФ составляет 8,3 ч.
Насколько часто такое будет происходить? Открытый вопрос, нужен эксперимент...
