2014 dxdy logo

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

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




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


19/12/10
1546
Nataly-Mak в сообщении #625107 писал(а):
Нет, не смогу.

Но Вы сможете написать программу проверяющую квадрат 12х12 на наличие монохромных прямоугольников?
Только проверяющую, и не делающую ничего более.
Уверен, сможете.

Используя эту программу, Вы сможете проверить все комбинации из четырёх своих блоков на наличие монохромных прямоугольников. Пример такой комбинации:
Код:
1 2
3 4
где числа это номера блоков.
Всего таких комбинаций 1296.
В результате получите базу данных запрещённых комбинаций из своих блоков.

Остаётся только написать процедуру перебора с возвратом для заполнения базовой матрицы, использующую эту базу данных.
Уверен, это Вы тоже сможете. :-)

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #625002 писал(а):
А что если существует решение C6N36, которому не соответствует никакой 6-сильный прямоугольник? Такое невозможно разве?
Вот, например, имеем решение C10N94, но пока никто не нашёл 10-сильный прямоугольник 84х10.

Конечно есть такой C6N36, например диагональное решение.

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


22/03/08

7154
Саратов
Цитата:
Так вот, для C = 6 не существует матрицы CxC из рассматриваемых нами блоков, зато существует 10 вариантов (C-1)x(C-1). Один из них...

(из статьи alexBlack)

Зато существует для С=6 базовая матрица 6х6 из других блоков.

Новый взгляд на строго диагональное решение C6N36

Строго диагональное решение C6N36 прекрасно вписывается в матричный метод.
Это 6 блоков 6х6:

(Оффтоп)

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

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

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

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

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

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

Эти блоки вообще никакие не латинские квадраты. Это не строго диагональные раскраски. В некоторых раскрасках отсутствуют первые цвета, однако максимальный цвет 6 присутствует во всех блоках.
Это базовая матрица 6х6:

Код:
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

Замечательная базовая матрица! Классический латинский квадрат 6-го порядка, построенный циклическим сдвигом.
Заполняем базовую матрицу приведёнными блоками в соответствии с их номерами. Получаем строго диагональное решение C6N36.

Изображение

Понятно, что я шла от готового строго диагонального решения C6N36. Автор этого решения Herbert Kociemba.
Точно так же можно построить строго диагональные решения C3N9, C4N16, C5N25, C7N49.

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


22/03/08

7154
Саратов
Этот 6-сильный прямоугольник 30х6 получен из 31-символьной строки Pavlovsky

Изображение

Вписывается ли это решение в теорию построения 6-сильных прямоугольников на основе ЛК и матрицы перестановок?
Или тут так: на основе некоторых классических ЛК 6-го порядка и матрицы перестановок можно построить 6-сильный прямоугольник 30х6, но не любой 6-сильный прямоугольник 30х6 можно построить таким способом :?:

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #624735 писал(а):
Любое решение можно представить как bipartite graph.


Не понял как это сделать? Таблица ЛК заполнена числами от 0 до N-1. Как такую таблицу интерпретировать как таблицу инцедентности двудольного графа?

-- Пн окт 01, 2012 09:34:31 --

Код:
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

Перестановка символов
(0,1,2,3,4,5)
(4,2,1,5,3,0)
Плюс нормализация
Получим:
Код:
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: Новый конкурс программистов
Сообщение01.10.2012, 07:38 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот набор из шести попарно ортогональных латинских прямоугольников 5х6, соответствующий приведённой в предыдущем посте 6-сильной раскраске 30х6:

(Оффтоп)

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

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

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

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

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

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

Латинские прямоугольники 5х6 обобщённые - полный аналог обобщённых латинских квадратов. Каждый прямоугольник заполнен числами от 1 до 6, и каждое из этих чисел использовано в прямоугольнике ровно 5 раз.

Кстати, из 31-символьной строки Pavlovsky мной получена 6-сильная раскраска 31х6 (пример приведён в книге), которой соответствует такой набор попарно ортогональных обобщённых латинских квадратов 6-го порядка с неполной последней строкой:

(Оффтоп)

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

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

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

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

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

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

Получить 6-сильный прямоугольник с числом строк больше 31 мне не удалось.
Выскажу гипотезу, что не существует 6-сильного прямоугольника mx6 при m>31.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #625002 писал(а):
На мой взгляд, ориентация на сильноокрашенный прямоугольник (применённая в последних трёх примерах Pavlovsky) сужает матричный метод.


Я исхожу из постулата, что все алгоритмы "алгебраического" типа эквивалентны.

-- Пн окт 01, 2012 09:46:24 --

Nataly-Mak в сообщении #625002 писал(а):
Кстати, alexBlack в своей статье не ориентировался на сильноокрашенные прямоугольники; он применял матричный метод в общем виде: вот есть 6 блоков 6х6, вот есть базовая матрица 5х5; заполняем базовую матрицу блоками и получаем решение; при этом интересный момент: для одного и того же исходного ЛК он находит 10 (!) различных базовых матриц. Почему 10 Эти все решения разные что ли будут? Или они будут изоморфные?]


Три исходных неизоморфных ЛК и все базовые матрицы 5х5
Код:
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
2,3,4,5,3,2,5,4,4,5,2,6,5,4,6,2
2,3,4,5,3,2,5,6,5,4,6,3,6,5,3,2
2,3,4,6,3,6,2,4,4,2,6,5,6,4,5,3
2,3,4,6,4,2,6,3,5,6,3,4,6,4,5,2
2,3,5,6,3,2,4,5,4,5,6,3,5,6,3,2
2,3,5,6,3,6,4,5,5,4,3,2,6,5,2,3
2,4,5,6,3,2,6,4,4,6,3,5,6,3,4,2
2,4,5,6,4,2,3,5,5,3,2,4,6,5,4,2

0,1,2,3,4,5,1,5,0,4,3,2,2,4,5,0,1,3,3,0,4,5,2,1,4,3,1,2,5,0,5,2,3,1,0,4
2,3,4,5,3,2,6,4,4,6,2,3,6,4,3,2
2,3,4,6,3,2,5,4,4,6,2,3,6,4,3,2
2,3,4,6,3,2,6,4,4,5,2,3,6,4,3,2
2,3,4,6,3,2,6,4,4,6,2,3,5,4,3,2
2,3,4,6,3,2,6,4,4,6,2,3,6,4,3,2

0,1,2,3,4,5,1,5,3,0,2,4,2,4,5,1,3,0,3,2,4,5,0,1,4,0,1,2,5,3,5,3,0,4,1,2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2
2,4,5,6,4,2,6,5,5,6,2,4,6,5,4,2


-- Пн окт 01, 2012 10:10:08 --

Nataly-Mak в сообщении #625002 писал(а):
А что если существует решение C6N36, которому не соответствует никакой 6-сильный прямоугольник? Такое невозможно разве?


Для сокращения перебора рассматривается некий класс решений. Естественно, наверняка существуют решения C6N36 без 6-сильноокрашенных прямоугольников. Более того решения с сильноокрашенными прямоугольниками имеют естественную верхнюю границу. Квадраты не могут иметь сторону больше C^2. А ведь наверняка существуют решения C6N37, может и больше.

-- Пн окт 01, 2012 10:21:29 --

Nataly-Mak в сообщении #625002 писал(а):
Вот эти 6 блоков:

(Оффтоп)

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

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

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

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

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

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



Составте ЛК из первых колонок ваших блоков:
Код:
4,5,6,1,2,3,
6,1,2,3,4,5,
5,6,1,2,3,4,
3,4,5,6,1,2,
1,2,3,4,5,6,
2,3,4,5,6,1

Этот ЛК будет изоморфным ЛК:
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: Новый конкурс программистов
Сообщение01.10.2012, 08:24 
Заблокирован
Аватара пользователя


22/03/08

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

Три исходных неизоморфных ЛК и все базовые матрицы 5х5
Код:
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
2,3,4,5,3,2,5,4,4,5,2,6,5,4,6,2
2,3,4,5,3,2,5,6,5,4,6,3,6,5,3,2
2,3,4,6,3,6,2,4,4,2,6,5,6,4,5,3
2,3,4,6,4,2,6,3,5,6,3,4,6,4,5,2
2,3,5,6,3,2,4,5,4,5,6,3,5,6,3,2
2,3,5,6,3,6,4,5,5,4,3,2,6,5,2,3
2,4,5,6,3,2,6,4,4,6,3,5,6,3,4,2
2,4,5,6,4,2,3,5,5,3,2,4,6,5,4,2

Почему у вас только 8 базовых матриц, а не 10, как у alexBlack для изоморфного вашему исходного ЛК?

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #625473 писал(а):
Почему у вас только 8 базовых матриц, а не 10, как у alexBlack для изоморфного вашему исходного ЛК?


Почему вопрос ко мне? Я свои 8 матриц показал. А alexBlack свои десять держит в секрете. :D

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


22/03/08

7154
Саратов
Потому что вы показываете 8 матриц, а alexBlack утверждает в статье, что он нашёл 10 матриц.
Вопросы alexBlack я задавать не могу (обещала больше не задавать).

-- Пн окт 01, 2012 09:36:50 --

Pavlovsky в сообщении #625468 писал(а):
Составте ЛК из первых колонок ваших блоков:
Код:
4,5,6,1,2,3,
6,1,2,3,4,5,
5,6,1,2,3,4,
3,4,5,6,1,2,
1,2,3,4,5,6,
2,3,4,5,6,1

Этот ЛК будет изоморфным ЛК:
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

То есть вы хотите сказать, что для моего набора блоков существует базовая матрица?

Какая же это матрица? Она такая, как для вашего ЛК №1?
То есть я могу взять любую из 8 приведённых вами матриц, заполнить её своими блоками и получить правильную раскраску? Я правильно вас поняла?

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #625027 писал(а):
А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.


Это не теория, а теорема!

Пусть у нас есть набор C перестановок, сведенных в ЛК CxC. И есть базовая матрица MxK. Такая что если в каждую ячейку подставить перестановку с соответствующим номером, то получится сльноокрашенный прямоугольник CMxK.
1) Поменяем в исходном ЛК две строки местами. Это эквивалентно, что в сильноокрашенном прямоугольнике мы поменяли местами M пар строк. Понятно что свойство сильноокрашенности останется неизменным.
2) Поменяем в исходном ЛК местами пару колонок (пусть колонки i и j). Это эквивалентно, тому что мы изменили нумерацию наших перестановок. Тогда если в базовой матрице поменять число i на j и наоборот. Мы получим тот же сильноокрашенный прямоугольник.
3) Сделаем в исходном ЛК замену символов. Если ту же операцию сделать и в сильноокрашенном прямоугольнике CMxK, то опять же свойство сильноокрашенности не изменится.

Три исходных ЛК 6х6 для которых можно построить матрицу 5х5, получены полным перебором.

-- Пн окт 01, 2012 10:51:57 --

Nataly-Mak в сообщении #625478 писал(а):
То есть я могу взять любую из 8 приведённых вами матриц, заполнить её своими блоками и получить правильную раскраску? Я правильно вас поняла?


Вот матрицы для ваших блоков.
Код:
2,3,4,5,3,5,2,4,5,2,6,3,6,4,3,2
2,3,4,5,3,6,2,4,4,2,5,3,6,5,3,2
2,3,4,6,3,6,2,5,4,2,5,3,5,4,3,2
2,3,4,6,4,6,2,5,5,2,6,4,6,4,3,2
2,3,5,6,3,5,2,4,4,2,6,3,5,4,3,2
2,3,5,6,4,6,3,5,5,2,6,4,6,5,4,3
2,4,5,6,3,6,2,4,4,2,6,3,6,5,4,2
2,4,5,6,3,6,2,5,5,3,6,4,6,5,4,3


-- Пн окт 01, 2012 11:01:25 --

dimkadimon в сообщении #625200 писал(а):
Конечно есть такой C6N36, например диагональное решение.


Есть очень большое подозрение, что диагональные решения основанные на теореме Зингера эквивалентны алгоритмам алгебраического типа! Над доказательством сейчас работаю.

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #625463 писал(а):
dimkadimon в сообщении #624735 писал(а):
Любое решение можно представить как bipartite graph.


Не понял как это сделать? Таблица ЛК заполнена числами от 0 до N-1. Как такую таблицу интерпретировать как таблицу инцедентности двудольного графа?


Не знаю как сделать для ЛК. А вот для оригинальной задачи знаю. У нас есть матрица А размером nxn. Пронумеруем колонки C1, C2, ..., Cn; пронумеруем строчки R1, R2, ..., Rn. Сделаем двудольный граф с вершинами R1...Rn слева и вершинами C1...Cn справа. Для любой ячейки А(r, c)=k красим ребро Rr-Cc в цвет k. Допустим в матрице А есть запрещенный прямоугольник A(r1,c1)=A(r1,c2)=A(r2,c1)=A(r2,c2), тогда в графе будет цикл длиной 4: Rr1-Cc1-Rr2-Cc2-Rr1.

Думаю тот же метод должен сработать для ЛК.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #625479 писал(а):
Nataly-Mak в сообщении #625027 писал(а):
А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.

Это не я писала.

Цитата:
Вот матрицы для ваших блоков.
Код:
2,3,4,5,3,5,2,4,5,2,6,3,6,4,3,2
2,3,4,5,3,6,2,4,4,2,5,3,6,5,3,2
2,3,4,6,3,6,2,5,4,2,5,3,5,4,3,2
2,3,4,6,4,6,2,5,5,2,6,4,6,4,3,2
2,3,5,6,3,5,2,4,4,2,6,3,5,4,3,2
2,3,5,6,4,6,3,5,5,2,6,4,6,5,4,3
2,4,5,6,3,6,2,4,4,2,6,3,6,5,4,2
2,4,5,6,3,6,2,5,5,3,6,4,6,5,4,3

Вы уверены, что при заполнении любой из этих матриц моими блоками (ещё раз подчёркиваю: моими блоками) получится правильное решение C6N36?
Среди этих матриц (самая первая) есть матрица, приведённая в статье alexBlack:

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

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #625486 писал(а):
Вы уверены, что при заполнении любой из этих матриц моими блоками


Не уверен. Ближе к вечеру по экспериментирую.

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


22/03/08

7154
Саратов
Повторила процедуру заполнения указанной базовой матрицы моими блоками. Как и в прошлый раз, получилось решение C6N30 c 294 ошибками:

Изображение

-- Пн окт 01, 2012 11:00:18 --

Кстати, whitefox от моих блоков пришёл к дугому исходному ЛК:

whitefox в сообщении #625009 писал(а):
Им соответствуют следующие перестановки:
Код:
1: 6 4 3 2 1 5
2: 5 1 2 3 4 6
3: 3 2 1 5 6 4
4: 1 5 4 6 2 3
5: 4 3 6 1 5 2
6: 2 6 5 4 3 1
Вывод: если существует базовая матрица, которую можно заполнить Вашими блоками, то эту же базовую матрицу можно заполнить и указанными перестановками.

Но эти перестановки составляют латинский квадрат.
А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.


-- Пн окт 01, 2012 11:02:55 --

Pavlovsky
а вы пришли от моих блоков к такому исходному ЛК:

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

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

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



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

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


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

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