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

[Pavlovsky]

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

Это счастливое озарение? Или Вы последовали совету dimkadimon, и применили программу nauty?

Быстро слабал програмку. Перебор всех перестановок символов с последующей нормализацией.

[whitefox]

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

Это вы шутите?

Нет, это вполне серьёзно.
Просто я радуюсь, что половину работы Вы уже сделали.
(Впрочем, на вторую половину времени может уйти больше чем на первую)

-- 29 сен 2012, 18:11 --

Pavlovsky в сообщении #624824 писал(а):

Быстро слабал програмку. Перебор всех перестановок символов с последующей нормализацией.

Круто, однако.
У меня на это духу не хватило.

-- 29 сен 2012, 18:16 --

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

Кстати, интересный вопрос: предположим, что не строго диагональное решение C5N25 не существует. Следует ли отсюда, что не строго диагональное решение C5N26 тоже не существует?

Если не существует диагональных решений C5N26, тогда точно не существует и диагональных решений C5N27.
А ответ на свой вопрос узнаете если потратите ещё несколько суток на прогон программы. (а это уже шутка )

[Nataly-Mak]

В продолжение трёх примеров Pavlovsky...

Это пример построения решения C6N36 из статьи alexBlack.

Исходный ЛК:

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

Базовая матрица

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

На всякий случай все 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
2 3 4 5 6 1

№2
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

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

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

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

И готовое решение C6N30 (без обрамления блоками Ci, Ri):

(Оффтоп)

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

В нормализованном виде исходный ЛК выглядит так:

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

ЛК, построенный циклическим сдвигом! Именно с таких ЛК, как мне помнится, начал изложение матричного метода Pavlovsky.

Pavlovsky
этот ЛК, конечно, обязан быть изоморфным одному из трёх ЛК, представленных вами.
По идее этот квадрат должен быть главным (самым первым) в ваших трёх примерах. Это же эталон матричного метода!
Теперь у вас есть программа проверки изоморфности ЛК 6-го порядка. Какому из ваших трёх ЛК изоморфен ЛК из статьи alexBlack?

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

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

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

И я привела выше свёртку блоков, для которой просила попытаться найти базовую матрицу. Увы, никто не попытался
А ведь у меня блоки строятся принципиально не так, как в примерах Pavlovsky. Нет никакой привязки к сильноокрашенному прямоугольнику. Есть 6 блоков 6х6, построенных по определённому правилу. Требуется определить, существует ли для этих 6 блоков базовая матрица и какого размера.
Никак не могу определить, какой исходный ЛК будет для моего набора блоков, если их строить так, как в последних трёх примерах Pavlovsky. Мне кажется, что такого исходного ЛК вообще не существует. Я ошибаюсь? Тогда кто-нибудь покажет мне этот исходный ЛК для моих 6 блоков?

Вот эти 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

-- Вс сен 30, 2012 08:22:13 --

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

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

Кстати, интересный вопрос: предположим, что не строго диагональное решение C5N25 не существует. Следует ли отсюда, что не строго диагональное решение C5N26 тоже не существует?

Если не существует диагональных решений C5N26, тогда точно не существует и диагональных решений C5N27.
А ответ на свой вопрос узнаете если потратите ещё несколько суток на прогон программы. (а это уже шутка )

whitefox
я серьёзно спрашиваю.
Вы отвечаете про C5N26 и C5N27, а мой вопрос был о решениях C5N25 и C5N26.
Если ответа на этот вопрос ни у кого нет (серьёзного!), тогда придётся прогнать программу и для решения C5N26.

[whitefox]

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

whitefox
я серьёзно спрашиваю.
Вы отвечаете про C5N26 и C5N27, а мой вопрос был о решениях C5N25 и C5N26.
Если ответа на этот вопрос ни у кого нет (серьёзного!), тогда придётся прогнать программу и для решения C5N26.

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

Доказано, что для C5N26 не существует строго диагональных раскрасок.
Если доказать,что для C5N26 не существует и нестрого диагональных раскрасок, то отсюда будет следовать, что и для всех больших N не существует диагональных раскрасок (как строгих так и нестрогих).

Серьёзный ответ ( ) на Ваш вопрос мне не известен, и иного способа решить его, кроме прогона программы, я не вижу.

-- 30 сен 2012, 08:45 --

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

И я привела выше свёртку блоков, для которой просила попытаться найти базовую матрицу. Увы, никто не попытался
А ведь у меня блоки строятся принципиально не так, как в примерах Pavlovsky. Нет никакой привязки к сильноокрашенному прямоугольнику. Есть 6 блоков 6х6, построенных по определённому правилу. Требуется определить, существует ли для этих 6 блоков базовая матрица и какого размера.
Никак не могу определить, какой исходный ЛК будет для моего набора блоков, если их строить так, как в последних трёх примерах Pavlovsky. Мне кажется, что такого исходного ЛК вообще не существует. Я ошибаюсь? Тогда кто-нибудь покажет мне этот исходный ЛК для моих 6 блоков?

Проделаем с вашими блоками следующую операцию:
в каждом блоке заменим все числа, кроме единицы, нулями.
Получим следующие шесть (0, 1)-матриц:

(Блоки)

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

0 0 0 0 1 0
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 0 1

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

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

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

0 1 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
1 0 0 0 0 0

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

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

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.

[Nataly-Mak]

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, они же у меня другие получатся
Блок №1:

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

Верно? То есть я взяла первый столбец исходного ЛК, а дальше +1 (по модулю 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

И так же все остальные блоки разные получаются.

Цитата:

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

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

[whitefox]

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

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

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

Если же заполнять базовую матрицу обобщёнными ЛК, то, возможно, уже не получится построить по ней сильный прямоугольник.

[Nataly-Mak]

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

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

На моём примере можете это показать?

Цитата:

Если же заполнять базовую матрицу обобщёнными ЛК, то, возможно, уже не получится построить по ней сильный прямоугольник.

Да, скорее всего. И вот тут как раз должно быть расширение метода (от случая, ориентированного на сильноокрашенные прямоугольники, разобранного Pavlovsky).

Кстати, сейчас собираюсь разобрать второй пример с 6-сильным прямоугольником 30х6 в моей книге. Там, по-моему, как раз обобщённые ЛК будут фигурировать. Но... надо посмотреть внимательнее.

[whitefox]

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

Но... тогда, если я буду строить блоки, исходя из этого ЛК так, как их надо строить в примерах Pavlovsky, они же у меня другие получатся

Предложенное мной построение перестановочной матрицы по латинскому квадрату не является отображением один в один.
Что с того, что получаются другие блоки?
Главный вывод остаётся верным:

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

если существует базовая матрица, которую можно заполнить Вашими блоками, то эту же базовую матрицу можно заполнить и указанными перестановками.

-- 30 сен 2012, 09:22 --

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

На моём примере можете это показать?

Простите, не совсем понял, что именно показать?
Ведь свой "разбор полётов" я основывал на Вашем примере.

-- 30 сен 2012, 09:28 --

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

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

Попросите Pavlosky проверить приведённый мной ЛК на изоморфизм одному из его ЛК. Если такой изоморфизм есть, то Вы получите базовую матрицу для своих блоков. А если нет, то это докажет, что для этих блоков базовая матрица не существует.

[Nataly-Mak]

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

А если нет, то это докажет, что для этих блоков базовая матрица не существует.

Нет, не докажет.
Во-первых, хотя бы потому, что Pavlovsky (в последних трёх примерах) рассматривал только случаи, когда существует максимальная базовая матрица 5х5.
В моём примере базовая матрица может существовать, но меньшего размера, скажем, 4х4 или 3х3, а может и вообще не существовать.

Во-вторых, потому, что я пока не уверена в правильности вашего главного вывода.
Так что, это докажет вам, но не докажет мне.

-- Вс сен 30, 2012 10:44:11 --

Вот пример, когда матрица перестановок имеет размер 4х4, а не 5х5:

Pavlovsky в сообщении #608484 писал(а):

0 1 2 3 4 5
1 3 0 2 5 4
2 5 4 0 3 1
3 4 5 1 0 2
4 0 1 5 2 3
5 2 3 4 1 0
ЛК 6х6 Наталии

2 4 6
3 2 4
5 3 2
Матрица перестановок. Строится решение тоже всего лишь C6N30.

[whitefox]

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

Нет, не докажет.
Во-первых, хотя бы потому, что Pavlovsky рассматривал только случаи, когда существует максимальная базовая матрица 5х5.
В моём примере базовая матрица может существовать, но меньшего размера, скажем, 4х4 или 3х3, а может и вообще не существовать.

Это не принципиально.
Методика остаётся та же.

Подобно тому как Pavlovsky нашёл три ЛК для базовых матриц 5х5,
можно найти ЛК для базовых матриц 4х4 и 3х3. И проверять изоморфизм приведённого мной ЛК с одним из этих ЛК.

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

Во-вторых, потому, что я пока не уверена в правильности вашего главного вывода.
Так что, это докажет вам, но не докажет мне.

Попытайтесь опровергнуть, и Вы убедитесь в его правильности.

[Nataly-Mak]

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

Это не принципиально.
Методика остаётся та же.
Подобно тому как Pavlovsky нашёл три ЛК для базовых матриц 5х5,
можно найти ЛК для базовых матриц 4х4 и 3х3. И проверять изоморфизм приведённого мной ЛК с одним из этих ЛК.

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

[whitefox]

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

Можно ещё проще: взять и проверить мой набор блоков на существование базовой матрицы.

Ничуть не проще.
Выполнить такую проверку "в лоб" это выполнить туже работу, что проделал Pavlovsky разыскивая свои ЛК.

[Nataly-Mak]

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

[whitefox]

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

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

Боюсь, что вашу задачу тоже придётся решать трижды.
Для базовых матриц 5х5, 4х4, 3х3.

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

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

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

[Nataly-Mak]

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

Боюсь, что вашу задачу тоже придётся решать трижды.
Для базовых матриц 5х5, 4х4, 3х3.

Но в моей задаче придётся проверять всего один набор блоков, то есть всего один исходный ЛК. Это точно та же задача, которую решал alexBlack, только для другого набора блоков. И он сделал полный перебор и нашёл 10 базовых матриц 5х5.

Цитата:

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

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