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

whitefox · 30.09.2012, 12:53

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

Нет, не смогу.

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

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

Код:

1 2
3 4

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

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

dimkadimon · 30.09.2012, 14:47

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

А что если существует решение C6N36, которому не соответствует никакой 6-сильный прямоугольник? Такое невозможно разве?
Вот, например, имеем решение C10N94, но пока никто не нашёл 10-сильный прямоугольник 84х10.

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

Nataly-Mak · 01.10.2012, 05:29

Цитата:

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

(из статьи alexBlack)

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

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

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

(Оффтоп)

Код:

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

Код:

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

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

Nataly-Mak · 01.10.2012, 06:31

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

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

Pavlovsky · 01.10.2012, 07:22

dimkadimon в сообщении #624735 писал(а):

Любое решение можно представить как bipartite graph.

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

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

Код:

Перестановка символов
(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

Nataly-Mak · 01.10.2012, 07:38

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

(Оффтоп)

Код:

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

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

(Оффтоп)

Код:

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

Pavlovsky · 01.10.2012, 07:39

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 блоков:

(Оффтоп)

Код:

Составте ЛК из первых колонок ваших блоков:

Код:

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

Nataly-Mak · 01.10.2012, 08:24

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 для изоморфного вашему исходного ЛК?

Pavlovsky · 01.10.2012, 08:26

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

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

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

Nataly-Mak · 01.10.2012, 08:29

Потому что вы показываете 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 приведённых вами матриц, заполнить её своими блоками и получить правильную раскраску? Я правильно вас поняла?

Pavlovsky · 01.10.2012, 08:49

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, например диагональное решение.

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

dimkadimon · 01.10.2012, 09:13

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.

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

Nataly-Mak · 01.10.2012, 09:18

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:

Код:

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

Pavlovsky · 01.10.2012, 09:33

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

Вы уверены, что при заполнении любой из этих матриц моими блоками

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

Nataly-Mak · 01.10.2012, 09:50

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

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

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

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

Им соответствуют следующие перестановки:

Код:

6 4 3 2 1 5
5 1 2 3 4 6
3 2 1 5 6 4
1 5 4 6 2 3
4 3 6 1 5 2
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

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

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