2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 112, 113, 114, 115, 116, 117, 118 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:33 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #624698 писал(а):
Ну так я и предположила, что мой ЛК не изоморфен ни одному из 3-х ЛК Pavlovsky.
В таком случае он должне быть среди 22 неизоморфных ЛК по ссылке. А его там нет!

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:37 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:40 
Аватара пользователя


21/02/10
1594
Екатеринбург
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 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:53 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #624707 писал(а):
Ну чего же он, такие нехорошие, нигде не описали свой алгоритм?


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


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 13:57 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #624701 писал(а):
Ваш ЛК обязан быть изоморфным одному из трех ЛК представленных мной.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:06 
Заслуженный участник
Аватара пользователя


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


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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:12 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #624728 писал(а):
Надо в тему "Латинские квадраты" запостить этот вопрос.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 14:23 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #624733 писал(а):
Nataly-Mak в сообщении #624728 писал(а):
Надо в тему "Латинские квадраты" запостить этот вопрос.

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение29.09.2012, 15:10 
Аватара пользователя


21/02/10
1594
Екатеринбург
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 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #624801 писал(а):
Вектор 1, 2, 1, ... это середина пути. :D

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 112, 113, 114, 115, 116, 117, 118 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group