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

[Nataly-Mak]

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

Этим методом я даже не смог найти 11х11 C=15...

Вы сделали полный перебор?

Вот alexBlack написал в своей статье, что для С=10 он сделал полный перебор.
Максимальная матрица у него получилась 8х8.

А на мой взгдяд (опять у нас с вами разный взгляд ) метод очень интересный, хотя бы тем, что он с ходу даёт решение для С=6, причём пока максимальное, ибо решение C6N37 ещё никто не получил, да и существует ли оно

Может быть, этот метод и не даст хорошее решение для С=15, но это ещё не факт.
Вот когда кто-нибудь сделает полный перебор, тогда это будет факт.

-- Пт сен 07, 2012 08:57:51 --

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

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

Что за метод? Опишите его здесь по-русски, пожалуйста. Желательно на конкретном примере.
Я почти не читаю сообщения на форуме конкурса по известной вам причине.

Но то условие, которое вы показали сейчас, оно действительно совпадает с условием Pavlovsky.

[alexBlack]

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

необходимо ли при поиске таких матриц условие, о котором писали Pavlovsky и whitefox?
Или вы искали матрицы, проверяя в лоб условие, что не возникает запрещённых прямоугольников? Что, может быть, как раз и равносильно условию Pavlovsky (?)

Да, можно сказать в лоб. Достаточно один раз проверить все четверки блоков и сохранить результат в матрице. Далее для проверки используем полученную матрицу.

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

Ещё вы пишете, что во второй строке (и во втором столбце) номера блоков можно расставить по неубыванию. Это значит, что вы допускаете наличие одинаковых номеров блоков. Правильно понимаю?

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

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

И последний вопрос: вы пробовали искать базовую матрицу для С=15?

Конечно, безрезультатно

[Nataly-Mak]

alexBlack в сообщении #615784 писал(а):

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

И последний вопрос: вы пробовали искать базовую матрицу для С=15?

Конечно, безрезультатно

Отрицательный результат - тоже результат.

Pavlovsky сообщал, что получил для С=15 матрицу 10х10.
dimkadimon жалуется, что не смог получить даже 11х11

А у вас какой результат?

-- Пт сен 07, 2012 11:48:56 --

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

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

dimkadimon
Вы называете свой метод базовым. Для какой группы С он даёт решения? Если базовый, то обязательно должен охватывать некоторую группу решений.

Например, изложенный мной на форуме конкурса метод можно назвать базовым, так как он годится для всех C=p^k+1, p - простое число, k>=1. При этом решения 1-го и 2-го класса по этому алгоритму получаются регулярные (то есть никакого перебора!); и только для решений 3-го класса я использую метод отжига при построении с-strong прямоугольников (добавление двух строк и одного цвета).

[whitefox]

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

Ничего не понял. Что за перестановки? Приведите пример.

Пример чего Вам привести? Перестановки?

Вот пожалуйста тождественная перестановка шести чисел: 1 2 3 4 5 6.
А вот беспорядочная перестановка тех же чисел: 3 4 1 5 6 2.
А всего перестановок шестого порядка 6!=720.
http://en.wikipedia.org/wiki/Permutation

Или Вас интересует пример заполнения базовой матрицы перестановками?

Вот пожалуйста:

F F C E D
F E E F B
E A F C F
B E F E E
E C A A E

где:
A= 1 2 3 4 5 6
B= 2 3 4 5 6 1
C= 3 4 5 6 1 2
D= 4 5 6 1 2 3
E= 5 6 1 2 3 4
F= 6 1 2 3 4 5

Можете убедится, что для этой матрицы перестановок выполняется приведённое мной условие:
всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть перестановка $\mathrm{M}=\mathrm{a}\mathrm{b^{-1}}\mathrm{d}\mathrm{c^{-1}}$ является беспорядочной.

[Pavlovsky]

http://infinitesearchspace.dyndns.org/c ... mment-1167

Проголосовал за 2 ноября.

[dimkadimon]

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

dimkadimon
Вы называете свой метод базовым. Для какой группы С он даёт решения? Если базовый, то обязательно должен охватывать некоторую группу решений.

Например, изложенный мной на форуме конкурса метод можно назвать базовым, так как он годится для всех C=p^k+1, p - простое число, k>=1. При этом решения 1-го и 2-го класса по этому алгоритму получаются регулярные (то есть никакого перебора!); и только для решений 3-го класса я использую метод отжига при построении с-strong прямоугольников (добавление двух строк и одного цвета).

Я наверное неправильно выразился. Я имел ввиду что у меня есть метод для построения базовой матрицы. Вот пример такой 5х5 матрицы:

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

Обозначим ету матрицу 1. Матрица 2 ето матрица 1 где все цвета сдвинуты на 1 итд. Теперь можем составить решение 25х25 поставля матрицы вот в таком порядке:

12345
23451
34512
45123
51234

В итоге получаем вот такое решение 25х25:

(Оффтоп)

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

-- 07.09.2012, 21:43 --

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

Вот пожалуйста:

F F C E D
F E E F B
E A F C F
B E F E E
E C A A E

где:
A= 1 2 3 4 5 6
B= 2 3 4 5 6 1
C= 3 4 5 6 1 2
D= 4 5 6 1 2 3
E= 5 6 1 2 3 4
F= 6 1 2 3 4 5

Можете убедится, что для этой матрицы перестановок выполняется приведённое мной условие:
всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть перестановка $\mathrm{M}=\mathrm{a}\mathrm{b^{-1}}\mathrm{d}\mathrm{c^{-1}}$ является беспорядочной.

Я знаю что такое перестановки, но не понимаю что такое матрица перестановок? То есть как из етого всего получить окончательное решение и как его преобразить с перестановкой М?

[Pavlovsky]

Цитата:

По поводу матриц $R_ + $ и $R_ \times$. Приведу пример:

0 0 0 0 0 0 0 0 
0 1 2 3 4 5 6 7 
0 2 3 4 5 6 7 1 
0 3 4 5 6 7 1 2 
0 4 5 6 7 1 2 3 
0 5 6 7 1 2 3 4 
0 6 7 1 2 3 4 5 
0 7 1 2 3 4 5 6 

0 1 2 3 4 5 6 7 
1 2 3 4 5 6 7 0 
2 5 6 7 1 2 3 5 
3 0 0 0 0 0 0 3 
4 6 7 1 2 3 4 2 
5 4 5 6 7 1 2 6 
6 3 4 5 6 7 1 1 
7 7 1 2 3 4 5 4 

Матрица $R_ \times$ была задана, а $R_ + $ найдена перебором, она даже не является латинским квадратом, но обе раскраски по теореме получаются правильные.

Сергей ты бы не мог более подробно описать процедуру построения. У меня по этим таблицам не получается получить решение.

[Nataly-Mak]

Pavlovsky
не надо игнорировать посты и статьи коллег.
Процедура построения подробно описана в статье alexBlack, о чём я сообщала здесь совсем недавно.

Вот какое решение C8N64 получается из приведённых матриц svb:



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

[whitefox]

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

Я знаю что такое перестановки, но не понимаю что такое матрица перестановок? То есть как из етого всего получить окончательное решение и как его преобразить с перестановкой М?

Матрица это просто прямоугольная таблица (двумерный массив), элементами которой могут быть объекты любой природы, в том числе и перестановки.

Когда svb и Pavlovsky ввели базовые матрицы, то их элементами были латинские квадраты, а числа заполнявшие матрицу - номера этих квадратов.

Причём использованные ими латинские квадраты полностью определяются клетками окрашенными в цвет 1.Например, латинский квадрат №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

полностью определяется прямоугольником:

1 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0

Обратите внимание, что этот прямоугольник фактически является матрицей перестановки 1 6 5 4 3 2 (не путать матрицу перестановки с базовой матрицей перестановок).

То есть фактически базовая матрица построенная svb и Pavlovsky есть матрица элементы которой суть перестановки.
Использованные ими перестановки являются элементами коммутативной группы. Именно поэтому моё условие:

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

всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть перестановка $\mathrm{M}=\mathrm{a}\mathrm{b^{-1}}\mathrm{d}\mathrm{c^{-1}}$ является беспорядочной.

преобразуется в условие:

всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть a+d-b-c<>0 (mod 6).

в силу коммутативности использованной группы перестановок.

Суть моего предложения в том, чтобы не ограничиваться коммутативными группами перестановок, а попробовать применить и некоммутативные.

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

Первый - каждую перестановку представить соответствующей матрицей, от которой перейти к латинскому квадрату.
Например в приведённой выше базовой матрице перестановок

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

F F C E D
F E E F B
E A F C F
B E F E E
E C A A E

где:
A= 1 2 3 4 5 6
B= 2 3 4 5 6 1
C= 3 4 5 6 1 2
D= 4 5 6 1 2 3
E= 5 6 1 2 3 4
F= 6 1 2 3 4 5

перестановку F с матрицей

0 0 0 0 0 1
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0

заменяем латинским квадратом

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

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

Второй способ - каждый столбец базовой матрицы перестановок записать как прямоугольник. В приведённом примере из базовой матрицы получим пять прямоугольников 5х6

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

которые являются попарно-ортогональными.
Добавим к ним ещё прямоугольник

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

и из полученного комплекта шести попарно-ортогональных прямоугольников строим 6-сильный прямоугольник 30х6. который стандартным образом расширяем до 6-окрашенного 36х36.
Этот способ я описывал выше.

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

[Nataly-Mak]

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

Когда svb и Pavlovsky ввели базовые матрицы, то их элементами были латинские квадраты, а числа заполнявшие матрицу - номера этих квадратов.

Уточнение: элементами базовых матриц могут быть не только классические, но и обобщённые латинские квадраты.
Как раз в только что приведённом решении svb элементами базовой матрицы являются обобщённые ЛК.

Кстати, предлагаю называть элементы базовой матрицы блоками; так называет их в своей статье alexBlack.

[whitefox]

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

Уточнение: элементами базовых матриц могут быть не только классические, но и обобщённые латинские квадраты.

Это ещё более широкое обобщение, чем предложенное мной.
Имхо, слишком широкое. Не представляю, как для С не являющихся степенями простых строить подобные базовые матрицы.

[Nataly-Mak]

Я имела в виду примеры, приведённые svb.
Вы ведь тоже говорили в той фразе о базовых матрицах svb (в частности).

[whitefox]

Nataly-Mak
В приведённом Вами примере обобщённые латинские квадраты также вполне однозначно определяются клетками окрашенными в цвет 1.
Например блок (2, 5):

5 6 7 8 1 2 3 4
3 4 5 6 7 8 1 2
2 3 4 5 6 7 8 1
8 1 2 3 4 5 6 7
7 8 1 2 3 4 5 6
6 7 8 1 2 3 4 5
5 6 7 8 1 2 3 4
7 8 1 2 3 4 5 6

однозначно определяется прямоугольником

0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0

Но этот прямоугольник уже не является перестановочной матрицей.

Не представляю, как строить базовую матрицу с использованием таких блоков для С не являющегося степенью простого, кроме полного перебора.

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

[Nataly-Mak]

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

Не представляю, как строить базовую матрицу с использованием таких блоков для С не являющегося степенью простого, кроме полного перебора.

Примеры, приведённые svb, как раз и относятся к степеням простых (С=8,9).
Даже и для С=8 (см. пример чуть выше) он находил вторую матрицу перебором (так написано в его сообщении). Базовая матрица у него была задана, а вот вторая матрица, которая и определяет, как строить блоки, была найдена перебором.

Как я понимаю, и для степеней простых нет другого способа построения таких нестандартных матриц, кроме перебора.

[Nataly-Mak]

Обратила внимание на такой интересный момент:
в примере svb базовая матрица была задана (в обозначениях svb базовая матрица - это Rx), а матрицу, определяющую блоки, он нашёл перебором, это матрица R+.

Так что проще: искать базовую матрицу в предположении, что мы знаем, как строить блоки, или искать по заданной базовой матрице матрицу, определяющую, как строить блоки?

Как нам кратко назвать вторую матрицу? Может быть, для неё есть какой-то общепринятый термин? А то очень длинно говорить "матрица, определяюшая, как строить блоки".
Для себя я назвала бы эту матрицу свёрткой блоков. Ведь в каждой строке этой матрицы кратко записан один блок позицией цвета 1 в строках этого блока.

Ещё один интересный момент.
whitefox чуть выше привёл пример, как он пришёл к базовой матрице для С=6 совсем другим путём.
Я выше тоже приводила такой пример для С=8.
Когда Pavlovsky показал матричный метод, я обнаружила среди своих решений решение очень похожее на построенное данным методом. Стала разбираться. Это решение у меня было построено совсем другим методом (кажется, на основе набора уникальных перестановок). Обнаружила, что базовая матрица у меня в точности совпадает с таблицей умножения в классическом конечном поле GF(8) за исключением последнего столбца, который у меня почему-то потерялся.
А вот вторая матрица R+ (свёртка блоков) в моём примере совсем другая.
Вот она:

1 8 7 6 5 4 3 2
8 1 6 7 4 5 2 3
7 6 1 8 3 2 5 4
6 7 8 1 2 3 4 5
5 4 3 2 1 8 7 6
4 5 2 3 8 1 6 7
3 2 5 4 7 6 1 8
2 3 4 5 6 7 8 1

Очень симпатичная матрица, симметрия относительно обеих главных диагоналей.

Так мы можем уже создавать банк матриц Rx и R+ для различных С.
Конкретные примеры всегда очень полезны для анализа.

-- Сб сен 08, 2012 06:49:13 --

Ещё раз повторю классические мвтрицы для С=8 - таблицы сложения и умножения в конечном поле GF(8), эти таблицы приводил svb.

[Замечу, что для меня привычнее матрицы без нулей. В своих исследованиях магических квадратов я всегда пользовалась именно такой формой записи.
Хотя многие программисты предпочитать начинать нумерацию с нуля.]

Базовая матрица Rx, таблица умножения:

1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8
1 3 5 7 4 2 8 6
1 4 7 6 8 5 2 3
1 5 4 8 7 3 6 2
1 6 2 5 3 8 4 7
1 7 8 2 6 4 3 5
1 8 6 3 2 7 5 4

Свёртка блоков R+, таблица сложения:

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

Выше я приводила решение C8N64, построенное по этим матрицам.

Уже начинаю анализ
Сравнила свою матрицу R+ с классической таблицей сложения.
Одна матрица легко переводится в другую такими заменами:

1 -> 1
2 -> 8
3 -> 7
4 -> 6
5 -> 5
6 -> 4
7 -> 3
8 -> 2

Так что у меня почти классический случай получился.

-- Сб сен 08, 2012 07:16:05 --

Ещё пример из статьи alexBlack - матрицы для С=6.
Базовая матрица Rx:

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

Свёртка блоков R+:

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

alexBlack утверждает в своей статье, что для данной свёртки блоков существует 10 различных базовых матриц.