2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 116, 117, 118, 119, 120, 121, 122 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение03.10.2012, 07:12 
Аватара пользователя


21/02/10
1594
Екатеринбург
Ход Конем.
Перестановка строк не нарушает свойство корректности решения. Составим из квадрата заполненного ходом коня, новый квадрат. Сначала выпишем нечетные строки, затем четные строки. У нас получится квадрат разбитый на два прямоугольника. Каждый прямоугольник заполнен диагоналями.

-- Ср окт 03, 2012 09:25:11 --

Код:
2 2 1 2 5
6 3 3 1 5
3 5 3 2 3
3 2 4 1 1
3 4 5 5 4

Такой естественно нет.
Все мои базовые матрицы нормализованы.
1) Первая колонка и строка заполнены перестановкой №1.
2) Номера перестановок во второй строке и колонке составляют возрастающую последовательность.
3) Во всех строках и колонках (кроме первой) нет одинаковых перестановок.

При заполнении матрицы перестановками из набора перестановок это корректные допущения.

При заполнении матрицы латинскими квадратами из заданного набора, свойства 1) и 3) в общем виде не верны.

В этом случае мы можем нормализовать только так:

1) Номера ЛК в первой строке и колонке составляют неубывающую последовательность.

В эту же тему. Сергей Беляев предложил способ нормализации таблицы умножения конечных полей.
http://svb.hut.ru/ALG/mono2.htm

 Профиль  
                  
 
 Re: Новый вид диагональных решений
Сообщение03.10.2012, 07:31 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #626346 писал(а):
Новый вид диагональных решений "ход конём"

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak Вы и Алексей Чернов заполняете матрицу блоками(ЛК). Я заполняю матрицу перестановками. Поэтому матрицы должны получаться абсолютно различными. Все совпадения случайны.
Если верен мой постулат "Все алгоритмы алгебраического типа эквивалентны", тогда матрицы полученные этими двумя способами должны иметь одинаковую размерность и должно существовать взаимнооднозначное преобразование одной матрицы в другую.

-- Ср окт 03, 2012 09:55:19 --

dimkadimon в сообщении #626354 писал(а):
Я тоже думал о таком виде решений. Потом понял что все эти решения основаные на ходах (например ход конём) эквивалентны диагональным решениям. Поэтому нет смысла их расматривать.


Смысл рассматривать есть. Разбиваем квадрат на прямоугольники. Каждый прямоугольник заполняем диагоналями. Очевидно это существенное ослоблание требований по сравнению с требованием диаганальности всего квадрата. А значит можно получить большую размерность решений.

 Профиль  
                  
 
 Re: Новый вид диагональных решений
Сообщение03.10.2012, 07:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #626354 писал(а):
Я тоже думал о таком виде решений. Потом понял что все эти решения основаные на ходах (например ход конём) эквивалентны диагональным решениям. Поэтому нет смысла их расматривать.

Что значит "эквивалентны диагональным решениям"?
Вы можете привести диагональное решение C4N13 "эквивалентное" моему решению С4N13 "ход конём"?

-- Ср окт 03, 2012 09:01:49 --

Pavlovsky в сообщении #626349 писал(а):
Код:
2 2 1 2 5
6 3 3 1 5
3 5 3 2 3
3 2 4 1 1
3 4 5 5 4

Такой естественно нет.
Все мои базовые матрицы нормализованы.
1) Первая колонка и строка заполнены перестановкой №1.
2) Номера перестановок во второй строке и колонке составляют возрастающую последовательность.
3) Во всех строках и колонках (кроме первой) нет одинаковых перестановок.

Вот данная матрица в нормализованном виде:

Код:
1 1 1 1 1
1 2 3 4 5
1 3 6 2 4
1 4 2 5 3
1 6 5 3 2

Такая нормализованная матрица у вас есть?
Точно такой нет, но какой она тогда изоморфна?

-- Ср окт 03, 2012 09:06:17 --

Pavlovsky в сообщении #626355 писал(а):
Nataly-Mak Вы и Алексей Чернов заполняете матрицу блоками(ЛК). Я заполняю матрицу перестановками.

А разве это не одно и то же?
Выше я показала ваш пример №1 очень подробно, применив оба способа:
1. заполнение базовой матрицы блоками;
2. заполнение базовой матрицы перестановками.

Что в лоб, что по лбу :D

-- Ср окт 03, 2012 09:17:15 --

whitefox в сообщении #624553 писал(а):
Nataly-Mak в сообщении #624406 писал(а):
whitefox
можно я приведу своё понимание первого примера Pavlovsky (см. цитату)?
Сама еле-еле разобралась :-) Когда разобралась, всё оказалось очень просто. Тот же самый матричный метод, который завёрнут в "матрицу перестановок, сильноокрашенный прямоугольник". Те же самые штанишки, только пуговки назад :D

Вы успешно применили оба, описанных выше, способа перехода от базовой матрицы перестановок к окончательному решению.


-- Ср окт 03, 2012 09:25:00 --

Уточню: приведённая базовая матрица whitefox заполняется теми же блоками, что и у alexBlack.
alexBlack назвал эти блоки в своей статье "блоки с циклическим сдвигом".

Вот они, эти 6 блоков:

(Оффтоп)

Код:
№1
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5

№2
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6

№3
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 1

№4
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2

№5
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3

№6
6 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4

Заполним любую базовую матрицу alexBlack этими блоками, получим правильное решение C6N36. Заполним любую базовую матрицу перестановками из ЛК (блок №1), получим правильное решение C6N36.
Правда, нам пока не показали все 10 базовых матриц, а показали только одну. Так что, высказанное утверждение подлежит проверке для любой из 10 матриц, оно проверено только для одной матрицы.

Заполним этими блоками (или перестановками из ЛК) базовую матрицу whitefox, получим правильное решение C6N36.

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


19/12/10
1546
Nataly-Mak в сообщении #626346 писал(а):
вам я ещё могу задавать вопросы? :D
Конечно можете. :D
Если я на какие-то Ваши вопросы не ответил, то только из-за личной невнимательности, извините.

Nataly-Mak в сообщении #626346 писал(а):
Поскольку процитированный вопрос повис в воздухе, позвольте переадресовать его вам, как автору приведённой базовой матрицы.
Существует всего 100 способов нормализации этой базовой матрицы.
В свободную минуту напишу программу сравнивающую их все с базовыми матрицами Pavlovsky.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #626357 писал(а):
А разве это не одно и то же?


Одно и тоже елси за основу берем ЛК полученный циклическим сдвигом и остальные блоки (ЛК) получаем циклическим сдвигом. А вот для вашего способа формирования набора ЛК матрицы получаются разными:
post625640.html#p625640

-- Ср окт 03, 2012 11:09:39 --

Код:
2 2 1 2 5
6 3 3 1 5
3 5 3 2 3
3 2 4 1 1
3 4 5 5 4


Код:
1 1 1 1 1
1 2 3 4 5
1 3 6 2 4
1 4 2 5 3
1 6 5 3 2


Пока я не умею корректно преобразовывать базовые матрицы. Например как из первой матрицы получилась вторая?

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #626366 писал(а):
Nataly-Mak в сообщении #626357 писал(а):
А разве это не одно и то же?


Одно и тоже елси за основу берем ЛК полученный циклическим сдвигом и остальные блоки (ЛК) получаем циклическим сдвигом.

Так ведь alexBlack именно так и берёт!
Сейчас речь не о моём способе, а о способе alexBlack и о вашем. Почему у вас с изоморфными исходными ЛК разное количество базовых матриц?

-- Ср окт 03, 2012 10:13:51 --

Pavlovsky в сообщении #626366 писал(а):
Код:
2 2 1 2 5
6 3 3 1 5
3 5 3 2 3
3 2 4 1 1
3 4 5 5 4


Код:
1 1 1 1 1
1 2 3 4 5
1 3 6 2 4
1 4 2 5 3
1 6 5 3 2


Пока я не умею корректно преобразовывать базовые матрицы. Например как из первой матрицы получилась вторая?

Этот вопрос к whitefox, он нормализовал матрицу, я ему чуть-чуть помогла :wink:

-- Ср окт 03, 2012 10:15:58 --

whitefox в сообщении #626365 писал(а):
Существует всего 100 способов нормализации этой базовой матрицы.
В свободную минуту напишу программу сравнивающую их все с базовыми матрицами Pavlovsky.

Ого, 100 способов :roll:
С нетерпением буду ждать ваших результатов.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #626357 писал(а):
Что значит "эквивалентны диагональным решениям"?


Берем диагональное решение NxN. Переставляем в нем строки так (1,N/2+1,2,N/2+2...N/2,N). Получается решение "Ход конем".

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #626371 писал(а):
Nataly-Mak в сообщении #626357 писал(а):
Что значит "эквивалентны диагональным решениям"?


Берем диагональное решение NxN. Переставляем в нем строки так (1,N/2+1,2,N/2+2...N/2,N). Получается решение "Ход конем".

Приведите диагональное решение C4N13 эквивалентное моему решению C4N13 "ход конём".
На конкретном примере лучше видно.

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


19/12/10
1546
Pavlovsky в сообщении #626355 писал(а):
Nataly-Mak Вы и Алексей Чернов заполняете матрицу блоками(ЛК). Я заполняю матрицу перестановками. Поэтому матрицы должны получаться абсолютно различными.

Если матрица может быть заполнена классическими латинскими квадратами, то она может быть заполнена и перестановками.
whitefox в сообщении #625009 писал(а):
Вывод: если существует базовая матрица, которую можно заполнить Вашими блоками, то эту же базовую матрицу можно заполнить и указанными перестановками.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #626373 писал(а):
Приведите диагональное решение C4N13 эквивалентное моему решению C4N13 "ход конём".


Из каждого диаганального решения можно получить решение ход конем. Обратное утверждение неверно. В общем случае, из решения ход конем можно получить квадрат разбитый на два прямоугольника заполненных диагоналями. Как, я описал чуть выше. У меня нет оцифрованного вашего решения C4N13. Но это ведь не трудно проделать процедуру: "Сначала выписать все нечетные строки, затем все четные".

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #626377 писал(а):

Из каждого диаганального решения можно получить решение ход конем. Обратное утверждение неверно.

Значит, уже не эквивалентны.
Вот не строго диагональное решение C4N13:

Код:
13,13,A,A,C,A,D,B,C,D,B,C,A,C,D,A,C,A,D,B,C,D,B,C,A,C,D,B,C,A,D,B,C,D,B,C,A,C,D,B,A,A,D,B,C
,D,B,C,A,C,D,B,A,A,D,B,C,D,B,C,A,C,D,B,A,A,D,B,C,D,B,C,A,C,D,B,A,A,D,C,C,D,B,C,A,C,D,B,A,A,
D,C,D,D,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B
,A,A,D,C,D,B,B,C,B,C,D,B,A,A,D,C,D,B,B,C,B,A,D,B,A,A,D,C,D,B,B,C,B,A,C

Можно из него получить решение C4N13 "ход конём"?
Покажите, пожалуйста, это решение "ход конём"?

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #626381 писал(а):
Значит, уже не эквивалентны.

Я этого не говорил. :D

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


19/12/10
1546
Pavlovsky в сообщении #626366 писал(а):
Пока я не умею корректно преобразовывать базовые матрицы. Например как из первой матрицы получилась вторая?

Для базовых матриц, соответствующих ЛК №1, допустимы (по крайней мере) следующие изоморфные преобразования:
1. перестановка столбцов;
2. перестановка строк;
3. прибавление по модулю шесть ко всем элементам одной строки одного и того же числа;
4. прибавление по модулю шесть ко всем элементам одного столбца одного и того же числа.

Примечание:
так как я при заполнении базовой матрицы не использую цифру 0, то в случае преобразований 3 и 4 полученный 0 заменяем 6.

Последовательность преобразований:
Код:
2 2 1 2 5
6 3 3 1 5
3 5 3 2 3
3 2 4 1 1
3 4 5 5 4

2 2 2 2 2
6 3 4 1 2
3 5 4 2 6
3 2 5 1 4
3 4 6 5 1

1 1 1 1 1
1 4 5 2 3
1 3 2 6 4
1 6 3 5 2
1 2 4 3 5

1 1 1 1 1
1 2 3 4 5
1 3 6 2 4
1 4 2 5 3
1 6 5 3 2

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


22/03/08

7154
Саратов
Вы отвечали на этот вопрос:
Pavlovsky в сообщении #626371 писал(а):
Nataly-Mak в сообщении #626357 писал(а):
Что значит "эквивалентны диагональным решениям"?


Берем диагональное решение NxN. Переставляем в нем строки так (1,N/2+1,2,N/2+2...N/2,N). Получается решение "Ход конем".


А вопрос, кстати сказать, был адресован не вам.
Не в свои вопросы не садись :D

-- Ср окт 03, 2012 11:43:58 --

Беру не строго диагональное решение C3N6:

Код:
6,6,A,C,C,B,A,A,C,C,B,A,A,B,C,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,B,C,A,B,A,B,C,C

Переставляю в нём строки, как рекомендовано в цитате. Получаю такое решение C3N6:

Изображение

Что-то оно не похоже на решение "ход конём".

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

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



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

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


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

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