2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 112, 113, 114, 115, 116, 117, 118 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:33 
Аватара пользователя
Nataly-Mak в сообщении #624698 писал(а):
Ну так я и предположила, что мой ЛК не изоморфен ни одному из 3-х ЛК Pavlovsky.
В таком случае он должне быть среди 22 неизоморфных ЛК по ссылке. А его там нет!

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

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

Pavlovsky в сообщении #624697 писал(а):
А вот как отловить изоморфизм относительно перестановки символов?! Перебирать все n! перестановок, а затем нормализовать?!

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:37 
Аватара пользователя
Эх-ма!
Ну и как же найти это преобразование, переводящее мой ЛК в один из этих 22?

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:40 
Аватара пользователя
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! вариантов перестановок цветов и отобрали одинаковые??

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:53 
Аватара пользователя
whitefox в сообщении #624707 писал(а):
Ну чего же он, такие нехорошие, нигде не описали свой алгоритм?


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


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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:57 
Аватара пользователя
Pavlovsky в сообщении #624701 писал(а):
Ваш ЛК обязан быть изоморфным одному из трех ЛК представленных мной.

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:06 
Аватара пользователя
Pavlovsky в сообщении #624710 писал(а):
dimkadimon в сообщении #621707 писал(а):
Здорово этот чувак (Brendan McKay) из моего старого университета ANU. Я его имя часто вижу в разных местах. Как жалко что я с ним не встречался


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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:12 
Аватара пользователя
А что, на нашем форуме нет специалистов по ЛК? :D
Надо в тему "Латинские квадраты" запостить этот вопрос.

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:22 
Аватара пользователя
Nataly-Mak в сообщении #624728 писал(а):
Надо в тему "Латинские квадраты" запостить этот вопрос.

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:23 
Аватара пользователя
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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:31 
Аватара пользователя
whitefox в сообщении #624733 писал(а):
Nataly-Mak в сообщении #624728 писал(а):
Надо в тему "Латинские квадраты" запостить этот вопрос.

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 15:10 
Аватара пользователя
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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 16:41 
Аватара пользователя
Pavlovsky
Теперь вижу, что мой ЛК изоморфен вашему ЛК №1.

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

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

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

Код:
1,2,1,2,3,4,3,5,1,5,...

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 17:14 
Аватара пользователя
Nataly-Mak в сообщении #624789 писал(а):
39 часов работает программа поиска не строго диагонального решения C5N25.
Базовый вектор на данный момент:
Код:
1,2,1,2,3,4,3,5,1,5,...

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

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

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 17:58 
Аватара пользователя
whitefox в сообщении #624801 писал(а):
Вектор 1, 2, 1, ... это середина пути. :D

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

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

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

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 112, 113, 114, 115, 116, 117, 118 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group