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

[whitefox]

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

Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую.

В этом примере я перепутал перестановки.

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

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

[Nataly-Mak]

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

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

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

[whitefox]

Начну немного издалека.

Следующие преобразования любое корректное решение 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

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

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

[Nataly-Mak]

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

[whitefox]

Упустил два момента.
Первый.

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

4. транспонирование переводит любое диагональное решение само в себя;

Это верно только если направление диагоналей "слева-вверх". А в случае направления диагоналей "слева-вниз" решение остаётся диагональным, но уже может не совпасть с исходным.

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

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

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

[Nataly-Mak]

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



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

[whitefox]

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

А вы что скажете, без вектора?

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

[Nataly-Mak]

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

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

А вы что скажете, без вектора?

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

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

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

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

1,2,3,4,1,1,3,1,3,3,2,2,4,2,4,4

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

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

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

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

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

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

[whitefox]

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

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

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

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

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

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

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

Верно, но один элемент можно сдвинуть и в уме.

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

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

Ну так ведь интересно же.

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

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

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

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

[Nataly-Mak]

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

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

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

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

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

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

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

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

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

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

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

[whitefox]

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

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

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

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

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
и т.д.

все равны с точность до циклического сдвига.

[Nataly-Mak]

Отлично. Закрепляем урок
Вот базовый вектор строго диагонального решения 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

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

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

[whitefox]

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

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

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

[Nataly-Mak]

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

[whitefox]

Всегда пожалуйста.