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

[Max Alekseyev]

* Crossposted in RU.ALGORITHMS

Hi, Dmitriy !

Replying to a message of Dmitriy Samsonov to All:

DS> Ортогональные латинские квадраты

[...]

DS> ╔═════════╗ ╔═════════╗
DS> · 1 2 3 4 · · 1 2 3 4 ·
DS> · 2 1 4 3 · · 4 3 2 1 ·
DS> · 3 4 1 2 · · 2 1 4 3 ·
DS> · 4 3 2 1 · · 3 4 1 2 ·
DS> ╚═════════ў ╚═════════ў
DS> ортогональны друг другу.

Лучше записывать в ячейках квадрата числа от 0 до n-1.

Hекоторые сабжи можно построить по формуле

m_{ji} = (a*i + b*j + c) mod n (i,j=1,2,...,n),

где a и b взаимно просты с n.
Если при этом a+b также взаимно просто с n, то квадрат будет к тому же
диагональным (магическим).

DS> Меня интересует, есть ли алгоритм, позволяющий БЫСТРО находить эти
DS> квадраты (просто перебор тут явно не подходит при большом n=10..25)?

Если n-нечетно и некратно 3-м, то пара диагональных латинских квадратов,
построенных по формулам

(a*i+b*j+c) mod n и (d*i+e*j+f) mod n,

будет ортогональна, если число a*e-b*d взаимно просто с n.

К сожалению, такой способ далеко не исчерпывает все возможности.

Разные алгоритмы построения ортогональных сабжей описаны в

Райзер Г. Дж. Комбинаторная математика. М.: Мир, 1966.

Холл М. Комбинаторика. М.: Мир, 1970.

Чебраков Ю.В., Шмагин В.В. Генерирование магических и взаимно ортогональных
обобщенных латинских квадратов / Деп. в РосКЦ ИТО 14.05.93, N 073.7210.374

Denes J. and Keedwell A.D. Latin squares and their application. Budapest:
Academiai Kiado, 1974.

Regards, ° °
Max ~

[Sergey Hashin]

Пpивет Dmitry!

В письме от Сpеда Май 06 1998, Max Alekseyev сообщал Dmitriy Samsonov:

MA> Hi, Dmitriy !

К сожалению, твое письмо пролетело мимо меня. Я увидел только ответ
Max Alekseev. Поэтому адреса твоего у меня нет.
Я люблю латинские квадраты, особенно пары ортогональных. Умею их строить.
о не быстро, а с естественной скоростью. Могу много чего про них сказать.
Имею полный список неэквивалентных квадратов 7*7, ортогональных пар размера 7*7
с точностью до разных отношений эквивалентности и многое другое.
Рад был бы встретить того, кому это тоже интересно.
апиши, если интересно.

С уважением Sergey - Четвеpг Май 07 1998 09:27.

[Moderator of RU MATH]

Hi, Sergey !

Replying to a message of Sergey Hashin to Dmitry Samsonov:

SH> К сожалению, твое письмо пролетело мимо меня.

Его письмо было в RU.ALGORITHMS

SH> Я увидел только ответ Max Alekseev. Поэтому адреса твоего у меня нет.

Посмотрел бы на клуджик из моего письма

@REPLY: 2:5036/10.25 3548c485
^^^^^^^^^^^^ вот и адрес DS

[...]

SH> апиши, если интересно.

Букву "H" настрой, а то наказать в следующий раз придется.

Moderator