2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 121, 122, 123, 124, 125, 126, 127 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 11:11 
Заслуженный участник
Аватара пользователя


19/12/10
1539
whitefox в сообщении #627487 писал(а):
Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую. :D
В этом примере я перепутал перестановки. :oops:

Должна быть перестановка 2 3 1, равная последовательному выполнению замен 1<->2, 1<->3.

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

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


22/03/08

7154
Саратов
whitefox в сообщении #627515 писал(а):
А указанную мной перестановку нужно применить к первой раскраске, чтобы получить вторую.

А я к первой и применила. Не очень обратила внимание на текст, а внимательно посмотрела на перестановку и сообразила, куда её надо применить :D

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


19/12/10
1539
Начну немного издалека.

Следующие преобразования любое корректное решение CxNy переводят в корректное решение CxNy:
1. произвольная перестановка столбцов;
2. произвольная перестановка строк;
3. произвольная перестановка цветов;
4. транспонирование.

Будем называть изоморфными два решения CxNy которые переводятся друг в друга при помощи некоторой комбинации указанных преобразований.

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

Рассмотрим ограничения, налагаемые последним требованием, на указанные изоморфные преобразования.

Начнём с конца:
4. транспонирование переводит любое диагональное решение само в себя;
3. произвольная перестановка цветов применима к диагональному решению без ограничений;
2. произвольная перестановка строк -- ограничения аналогичны ограничениям для произвольной перестановки столбцов.

Перестановку столбцов рассмотрим более внимательно.

Для нестрого диагональных решений единственно-возможная перестановка столбцов это перестановка приводящая к "зеркальной" раскраске (при этом изменяется направление диагоналей).

В случае строго диагональных решений добавляется ещё циклическая перестановка столбцов (при этом направление диагоналей не меняется).

Для канонических раскрасок выберем направление диагоналей "слева-вверх".

Таким образом для базовых векторов нестрого диагональных решений единственным изоморфным преобразованием является произвольная перестановка цветов.

А для базовых векторов строго диагональных решений добавляется ещё циклический сдвиг базового вектора.

Вот теперь, собственно, и перейдём к построению канонического базового вектора для строго диагонального решения.

Покажу на примере строго диагонального решения с базовым вектором:
Код:
1,4,1,4,2,2,1,3,3,2,3,2,4,4,3,1

Циклически сдвинем этот вектор так, чтобы первый и последний элементы были различными. Например, так:
Код:
1,4,2,2,1,3,3,2,3,2,4,4,3,1,1,4

Базовый вектор разбивается на блоки одинаковых цифр. Запишем вектор длин этих блоков:
Код:
1,1,2,1,2,1,1,1,2,1,2,1

Рассмотрим все циклические сдвиги базового вектора при которых первый и последний элементы различны, а соответствующие вектора длин блоков являются наименьшими в лексикографическом порядке.

Таких векторов два:
Код:
4,1,4,2,2,1,3,3,2,3,2,4,4,3,1,1
2,3,2,4,4,3,1,1,4,1,4,2,2,1,3,3

С вектором длин блоков:
Код:
1,1,1,2,1,2,1,1,1,2,1,2

Приведём каждый из них к каноническому виду:
Код:
1,2,1,3,3,2,4,4,3,4,3,1,1,4,2,2
1,2,1,3,3,2,4,4,3,4,3,1,1,4,2,2

Полученные вектора равны, но если бы это было не так, то мы бы взяли наименьший в лексикографическом порядке. Назовём такой вектор наименьшим каноническим базовым вектором.

Критерий изоморфности строго диагональных решений такой:
строго диагональные решения изоморфны тогда и только тогда, когда равны их наименьшие канонические базовые вектора.

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


22/03/08

7154
Саратов
Ой, спасибо, буду разбираться сейчас :?
Вроде всё поняла :-)
Сейчас возьму какое-нибудь строго диагональное решение тоже С4N16 и попробую найти его наименьший канонический базовый вектор, а заодно определить, изоморфно ли оно приведённому вами решению.

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


19/12/10
1539
Упустил два момента.
Первый.
whitefox в сообщении #627529 писал(а):
4. транспонирование переводит любое диагональное решение само в себя;
Это верно только если направление диагоналей "слева-вверх". А в случае направления диагоналей "слева-вниз" решение остаётся диагональным, но уже может не совпасть с исходным.

Второй.
Комбинация преобразований:
"зеркальное отражение", транспонирование, "зеркальное отражение"
приведёт к реверсу базового вектора.

Соответствующим образом нужно изменить и критерии изоморфности.

Но если транспонирование исключить из числа разрешённых изоморфных преобразований, то ничего менять не нужно.

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


22/03/08

7154
Саратов
whitefox
вот два строго диагональных решения C4N16, слева то, что вы рассмотрели в приведённом примере, справа - решение из Интернета:

Изображение

Пока не находила наименьший канонический базовый вектор второго решения.
Интуитивно: эти два решения неизоморфны.
А вы что скажете, без вектора? :D

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


19/12/10
1539
Nataly-Mak в сообщении #627543 писал(а):
А вы что скажете, без вектора? :D

Конечно могу и без вектора.
Они не изоморфны, так как у них разные вектора длин блоков (с точностью до циклического сдвига). :D

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


22/03/08

7154
Саратов
whitefox в сообщении #627547 писал(а):
Nataly-Mak в сообщении #627543 писал(а):
А вы что скажете, без вектора? :D

Конечно могу и без вектора.
Они не изоморфны, так как у них разные вектора длин блоков (с точностью до циклического сдвига). :D

Стоп! Не поняла. Так значит, есть более простой критерий?

Но у вашего решения сразу ведь не определяется вектор длин блоков, так как у базового вектора первое и последнее число одинаковые. Надо сначала делать циклический сдвиг базового вектора, следуя вашему примеру.
А у интернетовского решения сразу можно записать вектор длин блоков, не надо делать циклический сдвиг.
Так, я запуталась :-(

Уже нашла наименьший канонический вектор интернетовского решения, и он не такой, как у вашего решения:

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

И зачем же я его искала? :D

-- Сб окт 06, 2012 15:30:22 --

whitefox в сообщении #627529 писал(а):
Критерий изоморфности строго диагональных решений такой:
строго диагональные решения изоморфны тогда и только тогда, когда равны их наименьшие канонические базовые вектора.

Из этого я поняла: для того чтобы два строго диагональных решения были изоморфны, необходимо и достаточно, чтобы были равны их наименьшие канонические базовые вектора.
Но для того, чтобы сравнить эти вектора, их надо сначала найти.

Оказалось в приведённом мной примере, что можно определить изоморфность/неизоморфность двух строго диагональных решений и без наименьших канонических базовых векторов.

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


19/12/10
1539
Nataly-Mak в сообщении #627548 писал(а):
Стоп! Не поняла. Так значит, есть более простой критерий?
Равенство векторов длин блоков (с точностью до циклического сдвига) это необходимое условие изоморфности. Оно легко проверяется, и может использоваться для предварительной проверки.

Наименьший канонический вектор приходится искать только если вектора длин блоков равны.

Это же условие можно проверять и для нестрого диагональных решений.
Но здесь уже равенство должно быть точным (а не с точностью до циклического сдвига), и первый с последним элементы не обязаны различаться.

Nataly-Mak в сообщении #627548 писал(а):
Но у вашего решения сразу ведь не определяется вектор длин блоков, так как у базового вектора первое и последнее число одинаковые.
Верно, но один элемент можно сдвинуть и в уме.

Nataly-Mak в сообщении #627548 писал(а):
И зачем же я его искала? :D
Ну так ведь интересно же. :D

-- 06 окт 2012, 14:37 --

Nataly-Mak в сообщении #627548 писал(а):
Оказалось в приведённом мной примере, что можно определить изоморфность/неизоморфность двух строго диагональных решений и без наименьших канонических базовых векторов.

Только неизоморфность, так как равенство векторов длин блоков всего лишь необходимое условие изоморфности.

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


22/03/08

7154
Саратов
Начну с конца: интересно - да, но здесь это было не нужно :D

Теперь сначала: значит, сначала надо проверить необходимое условие изоморфности - равенство векторов длин блоков (предварительно циклически сдвигаем базовые вектора в обоих решениях так, чтобы первое и последнее числа в них были различны). В случае, если это условие не выполняется, сразу делаем вывод, что решения неизоморфны. Если же вектора длин блоков равны, тогда ищем наименьшие канонические вектора.

Теперь всё правильно поняла? :D

-- Сб окт 06, 2012 15:44:54 --

whitefox в сообщении #627552 писал(а):
Nataly-Mak в сообщении #627548 писал(а):
Оказалось в приведённом мной примере, что можно определить изоморфность/неизоморфность двух строго диагональных решений и без наименьших канонических базовых векторов.

Только неизоморфность, так как равенство векторов длин блоков всего лишь необходимое условие изоморфности.

Ну, да... если мы проверили и установили неизоморфность, то изоморфность уже проверять не нужно :D Если решения неизоморфны, то они не могут быть одновременно и изоморфными :wink:

-- Сб окт 06, 2012 15:50:09 --

Да, так значит, в этом примере интуиция меня не подвела :-)

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


19/12/10
1539
Nataly-Mak в сообщении #627554 писал(а):
Теперь сначала: значит, сначала надо проверить необходимое условие изоморфности - равенство векторов длин блоков (предварительно циклически сдвигаем базовые вектора в обоих решениях так, чтобы первое и последнее числа в них были различны). В случае, если это условие не выполняется, сразу делаем вывод, что решения неизоморфны. Если же вектора длин блоков равны, тогда ищем наименьшие канонические вектора.

Теперь всё правильно поняла? :D

Совершенно правильно. :D
Только уточню, что вектора длин блоков должны быть равны с точность до циклического сдвига. Например, вектора:
Код:
1,1,1,2,1,2,1,1,1,2,1,2
1,1,2,1,2,1,1,1,2,1,2,1
1,2,1,2,1,1,1,2,1,2,1,1
2,1,2,1,1,1,2,1,2,1,1,1
и т.д.
все равны с точность до циклического сдвига.

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


22/03/08

7154
Саратов
Отлично. Закрепляем урок :D
Вот базовый вектор строго диагонального решения C4N16 Herbert Kociemba:

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

будем сравнивать это решение с вашим решением.

Вектора длин блоков в обоих решениях одинаковые (с точностью до циклическтого сдвига):

Код:
2,1,1,1,2,1,2,1,1,1,2,1

Значит, пока не можем сделать вывод об изоморфности этих решений.
Надо искать наименьшие канонические базовые вектора обоих решений. Ну, для вашего решения вы уже такой вектор нашли. Осталось найти наименьший канонический базовый вектор для второго решения.
Ушла искать вектор :-)

-- Сб окт 06, 2012 16:46:32 --

Э-э-э-э...
а не зря ли я искала вектор и в этот раз?
Он у меня получился в точности такой, как у вас:

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

При этом точно так же есть два равных базовых вектора с наименьшими векторами длин блоков. И наименьший вектор длин блоков совпадает с вашим.
Так, эти два решения, значит, изоморфны.

Остался последний пример - от вас, господин учитель :-)
Ученица сомневается теперь, что есть два строго диагональных решения, у которых вектора длин блоков равны (с точностью до циклического сдвига), но сами решения неизоморфны.
Прошу пример, который развеет все сомнения :?

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


19/12/10
1539
Nataly-Mak в сообщении #627568 писал(а):
Остался последний пример - от вас, господин учитель :-)
Ученица сомневается теперь, что есть два строго диагональных решения, у которых вектора длин блоков равны (с точностью до циклического сдвига), но сами решения неизоморфны.
Прошу пример, который развеет все сомнения :?

Сожалею, но мне некогда эти заняться. :-(
У меня есть 2304 строго диагональных решения C4N16 (фактически это все диагональные решения чей базовый вектор начинается с 1). Можно поискать среди них.
Если желаете, могу прислать файл.

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


22/03/08

7154
Саратов
Хорошо, отложим этот вопрос до лучших времён.
Возможно, такой пример попадётся сам собой в другой ситуации.
Спасибо за урок.

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


19/12/10
1539
Всегда пожалуйста. :D

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 121, 122, 123, 124, 125, 126, 127 ... 130  След.

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



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

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


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

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