Новый конкурс программистов

[whitefox]

Nataly-Mak в сообщении #624698 писал(а):

Ну так я и предположила, что мой ЛК не изоморфен ни одному из 3-х ЛК Pavlovsky.
В таком случае он должне быть среди 22 неизоморфных ЛК по ссылке. А его там нет!

Он не обязан там быть, но обязательно существует изоморфизм Вашего ЛК с одним из этих 22-х.

-- 29 сен 2012, 13:35 --

Pavlovsky в сообщении #624697 писал(а):

А вот как отловить изоморфизм относительно перестановки символов?! Перебирать все n! перестановок, а затем нормализовать?!

Очень нудный способ, но похоже, что единственно возможный.

[Nataly-Mak]

Эх-ма!
Ну и как же найти это преобразование, переводящее мой ЛК в один из этих 22?

[Pavlovsky]

Nataly-Mak в сообщении #624698 писал(а):

Ну так я и предположила, что мой ЛК не изоморфен ни одному из 3-х ЛК Pavlovsky.В таком случае он должен быть среди 22 неизоморфных ЛК по ссылке. А его там нет!

Ваш ЛК обязан быть изоморфным одному из трех ЛК представленных мной.

-- Сб сен 29, 2012 15:46:59 --

whitefox в сообщении #624699 писал(а):

Очень нудный способ, но похоже, что единственно возможный.

Мама не горюй!
http://cs.anu.edu.au/~bdm/data/latin.html
есть файл с 1676267 неизоморфными относительно операции перестановки строк, колонок, символов ЛК 8х8. Это что они с начала получили все нормализованные ЛК (сколько их считать страшно) Затем из каждого получили 8! вариантов перестановок цветов и отобрали одинаковые??

[whitefox]

Pavlovsky в сообщении #624701 писал(а):

Мама не горюй!
http://cs.anu.edu.au/~bdm/data/latin.html
есть файл с 1676267 неизоморфными относительно операции перестановки строк, колонок, символов ЛК 8х8. Это что они с начала получили все нормализованные ЛК (сколько их считать страшно) Затем из каждого получили 8! вариантов перестановок цветов и отобрали одинаковые??

Ну чего же они, такие нехорошие, нигде не описали свой алгоритм?

[Pavlovsky]

whitefox в сообщении #624707 писал(а):

Ну чего же он, такие нехорошие, нигде не описали свой алгоритм?

dimkadimon в сообщении #621707 писал(а):

Здорово этот чувак (Brendan McKay) из моего старого университета ANU. Я его имя часто вижу в разных местах. Как жалко что я с ним не встречался

Надо у dimkadimon спросить.

[Nataly-Mak]

Pavlovsky в сообщении #624701 писал(а):

Ваш ЛК обязан быть изоморфным одному из трех ЛК представленных мной.

Кто это его обязал?
Пока не вижу доказательства этого факта.
Приведите преобразование, переводящее мой ЛК в один из трёх ЛК, представленных вами.

[whitefox]

Pavlovsky в сообщении #624710 писал(а):

dimkadimon в сообщении #621707 писал(а):
Здорово этот чувак (Brendan McKay) из моего старого университета ANU. Я его имя часто вижу в разных местах. Как жалко что я с ним не встречался


Надо у dimkadimon спросить.

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

[Nataly-Mak]

А что, на нашем форуме нет специалистов по ЛК?
Надо в тему "Латинские квадраты" запостить этот вопрос.

[whitefox]

Nataly-Mak в сообщении #624728 писал(а):

Надо в тему "Латинские квадраты" запостить этот вопрос.

Сделайте доброе дело.
А то я на сегодня свой лимит вопросов уже исчерпал.

[dimkadimon]

Pavlovsky в сообщении #624697 писал(а):

whitefox в сообщении #624695 писал(а):

PavlovskyА у Вас нет программы проверки изоморфизма ЛК?

Увы нет. Тщательно просмотрел литературу по ссылке об изоморфизме ЛК. Но ничего вменяемого не нашел. Нормализовать ЛК (сделать чтобы первая колонка и строка были вида 1,2,3...) легко. А вот как отловить изоморфизм относительно перестановки символов?! Перебирать все n! перестановок, а затем нормализовать?!

Любое решение можно представить как bipartite graph. Чтобы проверить изоморфность двух решений надо проверить изоморфность их графов. Roland Postle об етом уже говорил. Можно изпользовать igraph library или программу моего любимого чувака: http://cs.anu.edu.au/~bdm/nauty/. Вот в википедии: http://ru.wikipedia.org/wiki/%D0%98%D0% ... 0%BE%D0%B2

[Nataly-Mak]

whitefox в сообщении #624733 писал(а):

Nataly-Mak в сообщении #624728 писал(а):

Надо в тему "Латинские квадраты" запостить этот вопрос.

Сделайте доброе дело.
А то я на сегодня свой лимит вопросов уже исчерпал.

Уже сделала
topic15897-105.html

[Pavlovsky]

Nataly-Mak в сообщении #624711 писал(а):

Кто это его обязал?

Вот ваш ЛК. Числа уменьшены на единицу.

0,1,2,3,4,5,
1,0,3,2,5,4,
2,3,4,5,0,1,
3,2,5,4,1,0,
4,5,0,1,2,3,
5,4,1,0,3,2

Сделайте замену цветов
(0,1,2,3,4,5)
(4,5,1,0,3,2)
Полученный ЛК перестановкой строк и колонок нормализуйте.
У вас получится ЛК

0,1,2,3,4,5,
1,0,3,2,5,4,
2,3,5,4,1,0,
3,2,4,5,0,1,
4,5,1,0,2,3,
5,4,0,1,3,2

[Nataly-Mak]

Pavlovsky
Теперь вижу, что мой ЛК изоморфен вашему ЛК №1.

Ну так я и сразу это утверждала
Только преобразование у меня было неправильное.

-- Сб сен 29, 2012 17:56:25 --

39 часов работает программа поиска не строго диагонального решения C5N25.
Базовый вектор на данный момент:

1,2,1,2,3,4,3,5,1,5,...

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

[whitefox]

Nataly-Mak в сообщении #624789 писал(а):

39 часов работает программа поиска не строго диагонального решения C5N25.
Базовый вектор на данный момент:

1,2,1,2,3,4,3,5,1,5,...

Вектор 1, 2, 1, ... это середина пути.

-- 29 сен 2012, 17:34 --

Pavlovsky в сообщении #624757 писал(а):

Сделайте замену цветов
(0,1,2,3,4,5)
(4,5,1,0,3,2)
Полученный ЛК перестановкой строк и колонок нормализуйте.

Это счастливое озарение?
Или Вы последовали совету dimkadimon, и применили программу nauty?

[Nataly-Mak]

whitefox в сообщении #624801 писал(а):

Вектор 1, 2, 1, ... это середина пути.

Это вы шутите?

Ну, мне торопиться некуда.
"В гости к Богу не бывает опозданий" (c)

Кстати, интересный вопрос: предположим, что не строго диагональное решение C5N25 не существует. Следует ли отсюда, что не строго диагональное решение C5N26 тоже не существует?