2014 dxdy logo

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

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




На страницу Пред.  1 ... 82, 83, 84, 85, 86, 87, 88 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение03.08.2012, 13:32 
Аватара пользователя
Ах, до чего же хорошая игрушка :D

Сейчас загнала прямоугольник 94х100 10-color с 200 "дырками" в программу Эда и стала окрашивать "дырки".
Удалось свести количество "дырок" к 100 (то есть уменьшить ровно в 2 раза), и все "дырки" расположены в двух строках! Дальше ещё не пробовала окрашивать "дырки".

Фрагмент прямоугольника 94х100 10-color со 100 "дырками":

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение04.08.2012, 08:54 
Аватара пользователя
Интересная вырисовывается закономерность:
стандартная 3-сильная раскраска 9х4 позволила добавить к себе один цвет и 7 строк, в результате получилась 4-сильная раскраска 16х4.

Далее таким же способом получаем:
стандарнтная 4-сильная 16х5 --> 5-сильная 25х5 (плюс 9 строк);
стандартная 5-сильная 25х6 --> 6-сильная 31х6 (плюс 6 строк).

Любопытная картина!

Из 5-сильной раскраски 25х5, полученной этим способом, получила нерегулярное решение 25х25 5-coloring.

Любителям хаоса :D

Изображение

-- Сб авг 04, 2012 10:24:30 --

Такой набор из 5 попарно ортогональных обобщённых ЛК 5-го порядка получен из 5-сильной раскраски 25x5, показанной выше:

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

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

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

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

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

А шестой ЛК (ортогональный каждому из пяти) к этому набору можно добавить?
Или для обобщённых ЛК порядка n полный комплект попарно ортогональных квадратов состоит из n штук?

 
 
 
 Re: Новый конкурс программистов
Сообщение04.08.2012, 11:12 
Аватара пользователя
Nataly-Mak в сообщении #602946 писал(а):
А шестой ЛК (ортогональный каждому из пяти) к этому набору можно добавить?

Легко!
Получила 5-сильную раскраску 25х6, из неё прямоугольник 25х30 5-coloring.
Несколько интересных экспериментов с этим прямоугольником.
Получена раскраска 26х26 5-color с 4 дырками:

(Оффтоп)

Код:
26,26,A,A,A,E,A,A,B,B,B,A,B,B,C,C,C,B,C,C,D,D,D,C,D,D,E,E,E,D,A,A,E,D,A,E,B,B,A,E,B,A,C,C,B,
A,C,B,D,D,C,B,D,C,B,A,D,B,C,D,C,B,E,C,D,E,D,C,A,D,E,A,E,D,B,E,A,B,A,E,A,B,C,D,D,D,B,C,D,E,E,
E,C,D,E,A,A,A,D,E,A,B,B,B,E,A,B,B,B,E,E,B,C,C,C,A,A,C,D,D,D,B,B,D,E,E,E,C,C,E,A,A,B,C,A,D,B,C
,C,D,B,E,C,D,D,E,C,A,D,E,E,A,D,B,E,A,A,B,B,E,C,A,A,E,C,A,D,B,B,A,D,B,E,C,C,B,E,C,A,D,D,C,A,D,
B,D,E,C,D,A,C,E,A,D,E,B,D,A,B,E,A,C,E,B,C,A,B,D,A,C,D,C,C,B,E,A,E,D,D,C,A,B,A,E,E,D,B,C,B,A,
A,E,C,D,C,B,C,C,B,C,A,D,D,D,C,D,B,E,E,E,D,E,C,A,A,A,E,A,D,B,B,B,C,A,E,D,E,E,D,B,A,E,A,A,E,C,B
,A,B,B,A,D,C,B,C,C,B,E,C,E,A,B,D,B,D,A,B,C,E,C,E,B,C,D,A,D,A,C,D,E,B,E,B,D,D,D,D,D,A,B,E,E,E,
E,B,C,A,A,A,A,C,D,B,B,B,B,D,E,C,C,E,A,C,C,B,B,A,B,D,D,C,C,B,C,E,E,D,D,C,D,A,A,E,E,D,E,D,B,A,
C,C,E,E,C,B,D,D,A,A,D,C,E,E,B,B,E,D,A,A,C,C,A,D,A,B,A,D,C,E,B,C,B,E,D,A,C,D,C,A,E,B,D,E,D,B,
A,C,E,A,D,B,B,B,E,B,E,C,C,C,A,C,A,D,D,D,B,D,B,E,E,E,C,E,C,D,E,E,E,B,D,E,A,A,A,C,E,A,B,B,B,D,A
,B,C,C,C,E,B,C,D,E,E,B,D,C,A,A,A,C,E,D,B,B,B,D,A,E,C,C,C,E,B,A,D,D,D,E,B,E,B,A,C,A,C,A,C,B,D,
B,D,B,D,C,E,C,E,C,E,D,A,D,A,E,C,D,E,D,E,A,D,E,A,E,A,B,E,A,B,A,B,C,A,B,C,B,C,D,B,A,E,D,C,E,C,B
,A,E,D,A,D,C,B,A,E,B,E,D,C,B,A,C,A,E,D,A,C,E,A,C,B,B,D,A,B,D,C,C,E,B,C,E,D,D,A,C,D,A,E,E,B,C,
B,D,A,B,A,D,C,E,B,C,B,E,D,A,C,D,C,A,E,B,D,E,D,B,A,C,D,C,E,C,C,D,E,D,A,D,D,E,A,E,B,E,E,A,B,A,
C,A,A,B,C,D,B,A,E,C,@,D,B,A,E,C,@,D,B,A,E,C,@,D,B,A,E,C,@,D,B

Распределение цветов:
A 134
B 135
C 134
D 135
E 134
NULL 4

Далее получена раскраска 27х27 5-color с 8 дырками:

(Оффтоп)

Код:
27,27,A,A,A,E,A,A,B,B,B,A,B,B,C,C,C,B,C,C,D,D,D,C,D,D,E,E,E,E,D,A,A,E,D,A,E,B,B,A,E,B,A,C,C,
B,A,C,B,D,D,C,B,D,C,E,B,A,D,B,C,D,C,B,E,C,D,E,D,C,A,D,E,A,E,D,B,E,A,B,A,E,C,A,B,C,D,D,D,B,C,
D,E,E,E,C,D,E,A,A,A,D,E,A,B,B,B,E,A,B,B,B,B,E,E,B,C,C,C,A,A,C,D,D,D,B,B,D,E,E,E,C,C,E,A,A,A,B
,C,A,D,B,C,C,D,B,E,C,D,D,E,C,A,D,E,E,A,D,B,E,A,A,B,E,B,E,C,A,A,E,C,A,D,B,B,A,D,B,E,C,C,B,E,C,
A,D,D,C,A,D,B,B,D,E,C,D,A,C,E,A,D,E,B,D,A,B,E,A,C,E,B,C,A,B,D,A,C,D,D,C,C,B,E,A,E,D,D,C,A,B,
A,E,E,D,B,C,B,A,A,E,C,D,C,B,B,C,C,B,C,A,D,D,D,C,D,B,E,E,E,D,E,C,A,A,A,E,A,D,B,B,B,A,C,A,E,D,E
,E,D,B,A,E,A,A,E,C,B,A,B,B,A,D,C,B,C,C,B,E,D,C,E,A,B,D,B,D,A,B,C,E,C,E,B,C,D,A,D,A,C,D,E,B,E,
B,D,E,D,D,D,D,A,B,E,E,E,E,B,C,A,A,A,A,C,D,B,B,B,B,D,E,C,C,C,E,A,C,C,B,B,A,B,D,D,C,C,B,C,E,E,
D,D,C,D,A,A,E,E,D,E,B,D,B,A,C,C,E,E,C,B,D,D,A,A,D,C,E,E,B,B,E,D,A,A,C,C,A,E,D,A,B,A,D,C,E,B,
C,B,E,D,A,C,D,C,A,E,B,D,E,D,B,A,C,E,A,A,D,B,B,B,E,B,E,C,C,C,A,C,A,D,D,D,B,D,B,E,E,E,C,E,C,A,
D,E,E,E,B,D,E,A,A,A,C,E,A,B,B,B,D,A,B,C,C,C,E,B,C,D,D,E,E,B,D,C,A,A,A,C,E,D,B,B,B,D,A,E,C,C,C
,E,B,A,D,D,D,A,E,B,E,B,A,C,A,C,A,C,B,D,B,D,B,D,C,E,C,E,C,E,D,A,D,A,D,E,C,D,E,D,E,A,D,E,A,E,A,
B,E,A,B,A,B,C,A,B,C,B,C,D,B,C,A,E,D,C,E,C,B,A,E,D,A,D,C,B,A,E,B,E,D,C,B,A,C,A,E,D,C,A,C,E,A,C
,B,B,D,A,B,D,C,C,E,B,C,E,D,D,A,C,D,A,E,E,B,D,C,B,D,A,B,A,D,C,E,B,C,B,E,D,A,C,D,C,A,E,B,D,E,D
,B,A,C,C,D,C,E,C,C,D,E,D,A,D,D,E,A,E,B,E,E,A,B,A,C,A,A,B,C,B,A,C,E,B,D,@,A,C,E,B,D,@,A,C,E,B
,D,@,A,C,E,B,D,@,A,C,E,C,A,D,E,B,@,C,A,D,E,B,@,C,A,D,E,B,@,C,A,D,E,B,@,C,A,D

Распределение цветов в этой раскраске:
A 145
B 143
C 145
D 144
E 144
NULL 8

Следующая раскраска 28х28 с 12 дырками:

(Оффтоп)

Код:
28,28,A,A,A,E,A,A,B,B,B,A,B,B,C,C,C,B,C,C,D,D,D,C,D,D,E,E,E,D,E,D,A,A,E,D,A,E,B,B,A,E,B,A,C,
C,B,A,C,B,D,D,C,B,D,C,E,E,B,A,D,B,C,D,C,B,E,C,D,E,D,C,A,D,E,A,E,D,B,E,A,B,A,E,C,A,A,B,C,D,D,
D,B,C,D,E,E,E,C,D,E,A,A,A,D,E,A,B,B,B,E,A,B,C,B,B,B,E,E,B,C,C,C,A,A,C,D,D,D,B,B,D,E,E,E,C,C,E
,A,A,A,D,B,C,A,D,B,C,C,D,B,E,C,D,D,E,C,A,D,E,E,A,D,B,E,A,A,B,E,C,B,E,C,A,A,E,C,A,D,B,B,A,D,B,
E,C,C,B,E,C,A,D,D,C,A,D,B,E,B,D,E,C,D,A,C,E,A,D,E,B,D,A,B,E,A,C,E,B,C,A,B,D,A,C,D,B,D,C,C,B,
E,A,E,D,D,C,A,B,A,E,E,D,B,C,B,A,A,E,C,D,C,B,B,A,C,C,B,C,A,D,D,D,C,D,B,E,E,E,D,E,C,A,A,A,E,A,
D,B,B,B,A,B,C,A,E,D,E,E,D,B,A,E,A,A,E,C,B,A,B,B,A,D,C,B,C,C,B,E,D,C,C,E,A,B,D,B,D,A,B,C,E,C,E
,B,C,D,A,D,A,C,D,E,B,E,B,D,E,A,D,D,D,D,A,B,E,E,E,E,B,C,A,A,A,A,C,D,B,B,B,B,D,E,C,C,C,C,E,A,C,
C,B,B,A,B,D,D,C,C,B,C,E,E,D,D,C,D,A,A,E,E,D,E,B,B,D,B,A,C,C,E,E,C,B,D,D,A,A,D,C,E,E,B,B,E,D,
A,A,C,C,A,E,B,D,A,B,A,D,C,E,B,C,B,E,D,A,C,D,C,A,E,B,D,E,D,B,A,C,E,A,E,A,D,B,B,B,E,B,E,C,C,C,A
,C,A,D,D,D,B,D,B,E,E,E,C,E,C,A,A,D,E,E,E,B,D,E,A,A,A,C,E,A,B,B,B,D,A,B,C,C,C,E,B,C,D,D,D,E,E,
B,D,C,A,A,A,C,E,D,B,B,B,D,A,E,C,C,C,E,B,A,D,D,D,A,C,E,B,E,B,A,C,A,C,A,C,B,D,B,D,B,D,C,E,C,E,
C,E,D,A,D,A,D,A,E,C,D,E,D,E,A,D,E,A,E,A,B,E,A,B,A,B,C,A,B,C,B,C,D,B,C,D,A,E,D,C,E,C,B,A,E,D,
A,D,C,B,A,E,B,E,D,C,B,A,C,A,E,D,C,B,A,C,E,A,C,B,B,D,A,B,D,C,C,E,B,C,E,D,D,A,C,D,A,E,E,B,D,E,
C,B,D,A,B,A,D,C,E,B,C,B,E,D,A,C,D,C,A,E,B,D,E,D,B,A,C,E,C,D,C,E,C,C,D,E,D,A,D,D,E,A,E,B,E,E,
A,B,A,C,A,A,B,C,B,D,E,C,A,B,D,@,E,C,A,B,D,@,E,C,A,B,D,@,E,C,A,B,D,@,E,C,A,B,B,A,C,D,E,@,B,
A,C,D,E,@,B,A,C,D,E,@,B,A,C,D,E,@,B,A,C,D,C,E,D,A,B,@,C,E,D,A,B,@,C,E,D,A,B,@,C,E,D,A,B,@,C,E,D,A

Распределение цветов:
A 155
B 154
C 155
D 154
E 154
NULL 12

И ещё раскраска 29х29 с 16 дырками. Покажу эту раскраску на картинке:

Изображение

И наконец, нерегулярное решение 30х30 с 25 дырками.
Раньше здесь было показано регулярное решение 30х30 тоже с 25 дырками, которые занимали подквадрат 5х5.
В моём нерегулярном решении каждая дырка также даёт 5 ошибок при окрашивании в любой цвет. Итого в раскраске 125 ошибок, если дырки раскрасить в любой цвет.

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение04.08.2012, 12:20 
Аватара пользователя
Забыла сказать о распеределении цветов в раскрасках 29х29 и 30х30; в этих раскрасках цвета распределились равномерно: в первой каждый из 5 цветов занимает 165 ячеек, во второй - 175 ячеек. Это притом, что решения нерегулярные.

-- Сб авг 04, 2012 13:47:23 --

И, наконец, самое лучшее приближение к решению C5N26 - раскраска 26х26 5-color всего с одной дыркой. Выделила её из раскраски 30х30 с 25 дырками путём удаления строк и столбцов.
Моя раскраска отличается от той, что здесь приводили раньше (тоже с одной дыркой) тем, что она нерегулярная.
При этом дырка при окрашивании в любой цвет даёт 5 ошибок; каждый из 5 цветов занимает 135 ячеек. Всё точно так же, как в регулярном решении.

Изображение

Где-то в начале темы dimkadimon писал, что ему удалось получить раскраску 26х26 5-color всего с 2 ошибками. Значит, есть лучшее приближение, нежели раскраска с 5 ошибками.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.08.2012, 14:27 
Аватара пользователя
Nataly-Mak в сообщении #602985 писал(а):
Где-то в начале темы dimkadimon писал, что ему удалось получить раскраску 26х26 5-color всего с 2 ошибками. Значит, есть лучшее приближение, нежели раскраска с 5 ошибками.


Нет лучше 5 ошибок я не получал. Интересное у вас 26х26. С одной стороны оно выглядит хаотичным, а с другой оно полу-регулярное потому что 5х5 узоры повторяются слева на право.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.08.2012, 14:41 
Аватара пользователя
Да, всё верно.

dimkadimon в сообщении #580131 писал(а):
Да интересно кто первый найдёт больше чем С^2 для С>=5? Я нашёл 26х26 для С=5 где 5 неправильных прямоугольников. Вроде близко, но так далеко...

Что-то память мне стала изменять :D

Значит, лучшего приближения пока нет. А может, его и вообще нет :?:

Да и существование решения C5N26 мне кажется маловероятным.

 
 
 
 Re: Новый конкурс программистов
Сообщение05.08.2012, 11:13 
Аватара пользователя
Из того же квадрата 30х30 с 25 дырками путём удаления строк и столбцов получила своё лучшее приближение к решению C5N27.
В раскраске всего 4 дырки, каждая дырка при окрашивании в любой цвет даёт 5 ошибок. Итого в раскраске 20 ошибок при любом раскрашивании дырок. Каждый из 5 цветов (при наличии 4 дырок) занимает 145 ячеек.
Плохо то, что ни один цвет не является базовым (то есть не занимает 146 или более ячеек).

Изображение

У кого есть лучшее приближение к решению C5N27?

Кстати, и регулярное решение 27х27 тоже получается с 4 дырками (если обрезать то самое регулярное решение 30х30, в котором пустой подквадрат 5х5).
Ну, а моё решение нерегулярное.

 
 
 
 Re: Новый конкурс программистов
Сообщение05.08.2012, 11:48 
Аватара пользователя
Nataly-Mak в сообщении #603157 писал(а):
Из того же квадрата 30х30 с 25 дырками путём удаления строк и столбцов получила своё лучшее приближение к решению C5N27.
В раскраске всего 4 дырки, каждая дырка при окрашивании в любой цвет даёт 5 ошибок. Итого в раскраске 20 ошибок при любом раскрашивании дырок. Каждый из 5 цветов (при наличии 4 дырок) занимает 145 ячеек.
Плохо то, что ни один цвет не является базовым (то есть не занимает 146 или более ячеек).


Ух ты здорово! А можете выложить решение в виде цифр? Хочу посмотреть если его можно улучшить.

 
 
 
 Re: Новый конкурс программистов
Сообщение05.08.2012, 12:00 
Аватара пользователя
У меня нет в виде цифр, только в виде символов:

(Оффтоп)

Код:
27,27,A,A,A,E,A,A,B,B,B,A,B,B,C,C,B,C,C,D,D,C,D,D,E,E,D,E,E,E,D,A,A,E,D,A,E,B,B,A,E,B,C,C,B,A
,C,D,D,C,B,D,E,E,D,C,B,A,D,B,C,D,C,B,E,C,D,E,D,A,D,E,A,E,B,E,A,B,A,C,A,B,C,A,B,C,D,D,D,B,C,D
,E,E,E,C,E,A,A,A,D,A,B,B,B,E,B,C,C,C,B,B,B,E,E,B,C,C,C,A,A,C,D,D,B,B,D,E,E,C,C,E,A,A,D,D,A,B,
C,A,D,B,C,C,D,B,E,C,D,D,C,A,D,E,E,D,B,E,A,A,E,C,A,B,B,E,C,A,A,E,C,A,D,B,B,A,D,E,C,C,B,E,A,D,
D,C,A,B,E,E,D,B,D,E,C,D,A,C,E,A,D,E,B,D,B,E,A,C,E,C,A,B,D,A,D,B,C,E,D,C,C,B,E,A,E,D,D,C,A,B,
A,E,D,B,C,B,A,E,C,D,C,B,A,D,E,C,C,B,C,A,D,D,D,C,D,B,E,E,D,E,C,A,A,E,A,D,B,B,A,B,E,C,C,A,E,D,
E,E,D,B,A,E,A,A,E,B,A,B,B,A,C,B,C,C,B,D,C,D,D,C,E,A,B,D,B,D,A,B,C,E,C,E,C,D,A,D,A,D,E,B,E,B,E
,A,C,A,D,D,D,D,A,B,E,E,E,E,B,C,A,A,A,C,D,B,B,B,D,E,C,C,C,E,A,E,A,C,C,B,B,A,B,D,D,C,C,B,E,E,D,
D,C,A,A,E,E,D,B,B,A,A,D,B,A,C,C,E,E,C,B,D,D,A,A,C,E,E,B,B,D,A,A,C,C,E,B,B,D,D,A,B,A,D,C,E,B,
C,B,E,D,A,D,C,A,E,B,E,D,B,A,C,A,E,C,B,A,D,B,B,B,E,B,E,C,C,C,A,C,D,D,D,B,D,E,E,E,C,E,A,A,A,D,
D,E,E,E,B,D,E,A,A,A,C,E,A,B,B,D,A,B,C,C,E,B,C,D,D,A,C,E,E,B,D,C,A,A,A,C,E,D,B,B,D,A,E,C,C,E,B
,A,D,D,A,C,B,E,E,B,E,B,A,C,A,C,A,C,B,D,B,B,D,C,E,C,C,E,D,A,D,D,A,E,B,E,C,D,E,D,E,A,D,E,A,E,A,
B,A,B,A,B,C,B,C,B,C,D,C,D,C,D,A,E,D,C,E,C,B,A,E,D,A,D,C,A,E,B,E,D,B,A,C,A,E,C,B,D,B,A,C,E,A,
C,B,B,D,A,B,D,C,C,B,C,E,D,D,C,D,A,E,E,D,E,B,A,C,B,D,A,B,A,D,C,E,B,C,B,E,A,C,D,C,A,B,D,E,D,B,
C,E,A,E,C,D,C,E,C,C,D,E,D,A,D,D,E,E,B,E,E,A,A,C,A,A,B,B,D,B,B,B,@,A,D,C,E,B,@,A,D,C,E,B,A,D,
C,E,B,A,D,C,E,B,A,D,C,E,D,@,B,A,E,C,D,@,B,A,E,C,D,B,A,E,C,D,B,A,E,C,D,B,A,E,C

 
 
 
 Re: Новый конкурс программистов
Сообщение05.08.2012, 13:22 
Аватара пользователя
Простое случайное перемешивание регулярного квадрата:
Изображение
Можно перемешивать и с дырками.

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

Заинтересовал вопрос изоморфизма С-сильных раскрасок.

Вот стандартная 4-сильная раскраска 16х5, построенная на основе полного комплекта попарно ортогональных ЛК 4-го порядка, приведённого в моей статье (см. рис.1):

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

Так она выглядит в программе Эда:

Изображение

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

В этой же статье мной получены группы попарно ортогональных ЛК 4-го порядка неизоморфные приведённой выше группе нормализованных ЛК.
Я взяла неизоморфную группу, изображённую на рис. 4 в указанной статье, и построила на её основе 4-сильную раскраску 16х5:

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

Так эта раскраска выглядит в программе Эда:

Изображение

Если не ошибаюсь, получена 4-сильная раскраска неизоморфная показанной выше раскраске.

Точно так же я построила 9-сильную раскраску 81х10 сначала на основе полного комплекта попарно ортогональных ЛК 9-го порядка, построенного в Maple (этот комплект приведён в моей статье "Группы взаимно ортогональных латинских квадратов").
Затем построила 9-сильную раскраску на основе другого комлекта попарно ортогональных ЛК 9-го порядка (он тоже приведён в указанной статье; я взяла его из статьи “Handbook of Combinatorial Design”). Эта группа MOLS неизоморфна группе, построенной в Maple.
В результате получилась 9-сильная раскраска 81х10 неизоморфная первой раскраске.

А вот построить неизоморфную 19-сильную раскраску 361х20 я не умею.
Построила только одну - на основе полного комплекта попарно ортогональных ЛК 19-го порядка. Неизоморфного комплекта MOLS 19-го порядка я не знаю.

Кто-нибудь знает, как построить неизоморфную 19-сильную раскраску 361х20?

 
 
 
 Re: Новый конкурс программистов
Сообщение06.08.2012, 14:52 
Аватара пользователя
Nataly-Mak в сообщении #603381 писал(а):
Если не ошибаюсь, получена 4-сильная раскраска неизоморфная показанной выше раскраске.


Представленные вами раскраски изоморфны. Относительно операции перестановки строк (колонок) и операции замены цветов.

 
 
 
 Re: Новый конкурс программистов
Сообщение06.08.2012, 15:04 
Аватара пользователя
Покажите, пожалуйста, какая замена цветов и какие перестановки строк и колонок.
Лучше это показывать не на раскрасках, а на их числовых кодах, которые тоже приведены.

Первая и последняя колонки в этих раскрасках полностью совпадают. Как надо переставить остальные три колонки в первой раскраске, чтобы получить вторую раскраску?

Получается, что и группы попарно ортогональных ЛК 4-го порядка, из которых построены эти раскраски, тоже изоморфны?
Но какими изоморфными преобразованиями они переводятся друг в друга? Я пока не вижу.

Первая группа MOLS (группа нормализованных ЛК; она приводится во многих статьях):

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

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

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

Вторая группа MOLS (построена мной):

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

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

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


-- Пн авг 06, 2012 16:49:20 --

Группы MOLS вроде переводятся одна в другую.
Если:
1. повернуть все квадраты второй группы на 90 градусов против часовой стрелки и отразить относительно вертикальной оси симметрии;
2. сделать замену:
1 -> 4, 2 -> 3, 3 -> 2, 4 ->1;
3. одинаково переставить строки в полученных ЛК.

Если все эти преобразования относятся к классу изоморфных преобразований, то две группы MOLS действительно изоморфны.

А что у нас в раскрасках?
Как делать замену цветов и как переставлять колонки (строки)?
Сейчас буду разбираться.
Ну, наверное точно так же, как и в самих ЛК.
Меня смутили совпадающие первая и последняя колонки. Ну, на них не надо обращать внимание, они так - сбоку припёка :D

ОК. Всё поняла.

Так, хорошо. А есть ли 4-сильная раскраска 16х5 неизоморфная двум приведённым?

 
 
 
 Re: Новый конкурс программистов
Сообщение06.08.2012, 16:17 
Аватара пользователя
Nataly-Mak в сообщении #603435 писал(а):
Группы MOLS вроде переводятся одна в другую.
Если:
1. повернуть все квадраты второй группы на 90 градусов против часовой стрелки и отразить относительно вертикальной оси симметрии;
2. сделать замену:
1 -> 4, 2 -> 3, 3 -> 2, 4 ->1;
3. одинаково переставить строки в полученных ЛК.

Если все эти преобразования относятся к классу изоморфных преобразований, то две группы MOLS действительно изоморфны.

Хе-х... можно гораздо проще :?
просто повернуть на 90 градусов против часовой стрелки и переставить одинаково строки, никаких замен делать не надо.

-- Пн авг 06, 2012 17:49:44 --

Такой вопрос ещё по изоморфным раскраскам (хотя и на предыдущие ещё не получила ответ :-( ):
здесь приведены две 17-сильные раскраски 289х18.
Первая раскраска построена на основе полного комплекта попарно ортогональных ЛК 17-го порядка.
Вторая получена некоторыми преобразованиями первой, в число которых входит и метод отжига.

Вопрос: являются ли эти раскраски изоморфными?
Как это вообще проверить?

 
 
 
 Re: Новый конкурс программистов
Сообщение07.08.2012, 06:10 
Аватара пользователя
Pavlovsky в сообщении #603423 писал(а):
Представленные вами раскраски изоморфны. Относительно операции перестановки строк (колонок) и операции замены цветов.

А как можно заменять цвета в раскраске?

Ну, понятно, что можно по схеме:
A -> B -> C -> D - > A (циклическая замена).

Далее, можно заменить цвета по аналогии с заменой, которую в ЛК называют трансформацией тождественной перестановки. То есть заменить тождественную перестановку 1,2,3,...,n любой другой перестановкой. Понятно, что и с цветами можно сделать то же самое.
Такая замена выражает факт равноправности всех цветов в раскраске.

[Кстати, циклическая замена - это частный случай трансформации тождественной перестановки:
1 2 3 4
2 3 4 1]

Какая ещё перекраска (замена цветов) возможна в раскракске?

-- Вт авг 07, 2012 07:14:29 --

В код раскраски вкралась опечатка:

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

Предпоследняя строка правильно: 3,3,1,2,4.
На изображении раскраски всё правильно.

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 82, 83, 84, 85, 86, 87, 88 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group