Талицы Кэли для квазигрупп (количество латинских квадратов)

[ellipse]

Как вычислить число латинских квадратов порядка n? Нужно в явном виде перебрать все квадраты (насколько я знаю эта задача NP полная) или есть более быстрая формула?

Латинский квадрат это таблица кэли квазигруппы в общем случае с правым и левым обратным элементом.

Есть какие-то особые алгоритмы нахождения таблиц и их кол-ва с двусторонним обратным элементом, нейтральным элементом, двусторонним нейтральным элементом?

Есть ли какие-то особые алгоритмы определения ассоциативных таблиц и их кол-ва?

Что по этой теме почитать (желательно на рус)?

[maxal]

Подсчёт латинских квадратов порядка $n$ - очень сложная задача. На данный момент ответ известен только для $n\leq 11$.

[VAL]

ellipse в сообщении #263224 писал(а):

Как вычислить число латинских квадратов порядка n? Нужно в явном виде перебрать все квадраты (насколько я знаю эта задача NP полная) или есть более быстрая формула?

Латинский квадрат это таблица кэли квазигруппы в общем случае с правым и левым обратным элементом.

Есть какие-то особые алгоритмы нахождения таблиц и их кол-ва с двусторонним обратным элементом, нейтральным элементом, двусторонним нейтральным элементом?

А какие порядки Вас интересуют? Для небольших $n \ (\le7)$ у меня таблички Кэли для всех луп где-то валяются. Они даже разбиты на классы изоморфных луп.

Цитата:

Есть ли какие-то особые алгоритмы определения ассоциативных таблиц и их кол-ва?

Хороших не знаю. Но, как ни странно, лобовая проверка проходит довольно быстро. Казалось бы, цикл глубины 3... Но, в том-то и дело, что в подавляющем большинстве случаев тождество ассоциативности нарушается практически сразу же.

Цитата:

Что по этой теме почитать (желательно на рус)?

Про латинские квадраты - М.Холл. "Комбинаторика".
Про квазигруппы и лупы - В.Д.Белоусов "Элементы теории квазигрупп и луп".

[ellipse]

maxal в сообщении #264300 писал(а):

Подсчёт латинских квадратов порядка $n$ - очень сложная задача. На данный момент ответ известен только для $n\leq 11$.

Я понимаю что очень сложная. Вопрос в том, равная ли по сложности задача нахождения числа квадратов порядка n задаче явного нахождения всех квадратов порядка n?

-- Ср ноя 25, 2009 22:31:54 --

VAL в сообщении #264463 писал(а):

А какие порядки Вас интересуют? Для небольших $n \ (\le7)$ у меня таблички Кэли для всех луп где-то валяются. Они даже разбиты на классы изоморфных луп.

Спасибо. Пока меня интересует исключительно теория)

[maxal]

ellipse в сообщении #265337 писал(а):

Я понимаю что очень сложная. Вопрос в том, равная ли по сложности задача нахождения числа квадратов порядка n задаче явного нахождения всех квадратов порядка n?

Нет. Задача нахождения количества проще перебора - хотя бы потому, что для $n=11$ количество известно, но оно настолько огромно, что перебор всех латинских квадратов $11\times 11$ неосуществим в обозримое время.

[iig]

Я советую использовать представление перестановок, крвтко описанном на моем сайте.
Кроме того, для классификации квазигрупп и луп можно применять циклическое представление, тут по крайней мере проявляется структура, эта тема сейчас мне интересна.

[bot]

ellipse в сообщении #263224 писал(а):

Есть ли какие-то особые алгоритмы определения ассоциативных таблиц и их кол-ва?

Считал когда-то, ещё на БЭСМ-6 полугруппы 5-го порядка - их более 1000. Перебирать группоиды, тестировать на ассоциативность, а потом ещё и разбивать по изоморфизму/антиизоморфизму было за-а-ведомо безнадёжно. Добавлял внешнюю единицу и использовал представление частичными отображениями. Американцы в это же время считали 5 и 6-элементные. Мне надо было для дела, а им, как мне кажется, для спортивного интереса - типа демонстрировали возможности своей новой ЭВМ на трудоёмкой задаче.