2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 100, 101, 102, 103, 104, 105, 106 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение06.09.2012, 05:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon
а решения для С=15 вас уже не интересуют? Вы думаете, что найденное вами решение C15N198 максимальное?
Я в этом очень сильно сомневаюсь.

Что касается не строго диагональных решений...
Не факт, что они не существуют для C>10. То есть даже наоборот: для C>10 они существуют, но важно - какие CXNY. Например, существуют строго диагональные решения C12N133 и C14N183. А вот не строго диагональные, как мне кажется, могут существовать и для бОльших N.

А что задача нахожденя не строго диагональных решений намного сложнее, нежели строго диагональных, так ведь задача от этого становится только интереснее :wink: Разве не так?

Выше Pavlovsky выкладывал небольшое исследование по этой проблеме (именно для не строго диагональных решений!).
Думаю, это исследование надо продолжить.
Мне очень интересны диагональные решения.

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


01/06/12
980
Adelaide, Australia
Nataly-Mak в сообщении #615354 писал(а):
dimkadimon
а решения для С=15 вас уже не интересуют? Вы думаете, что найденное вами решение C15N198 максимальное?
Я в этом очень сильно сомневаюсь.

Интересуют конечно. Но на данный момент нет идей как их получить. Самое лучшее C15N199 у меня имеет 157 ошибок, а это очень далеко!

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


22/03/08

7154
Саратов
А матричный метод вы исключаете из рассмотрения (был показан Pavlovsky, описан в статье alexBlack)?

Ведь если удастся найти базовую матрицу 13х13, это даст решение C15N210!

Я предлагаю решать задачу сообща. Написать хорошую программу и распределить перебор между всеми желающими участвовать в проекте.

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


21/02/10
1594
Екатеринбург
Vitaly12 в сообщении #615291 писал(а):
Может быть я пропустил: на форуме infinitesearchspace где-нибудь говорилось когда должен начаться следующий конкурс?


Цитата:
the beta testers for the next contest have been notified and we will start working to get the next one wired up and ready. I don't have a start date yet, but I'm thinking late October, maybe my birthday on the 30th.


-- Чт сен 06, 2012 09:29:33 --

whitefox в сообщении #615174 писал(а):
Это мираж. Одноцветные строки здесь не причём.

whitefox Спасибо за мини исследование. Сейчас как раз неспешно разбираюсь, где миражи, а где что то ценное.

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


22/03/08

7154
Саратов
Pavlovskу
а мои посты вы не читаете? Я у вас в игноре?
Лады. Тоже заношу вас в игнор.

А что там неспешно разбираться? Очевидно, что вы создали искусственную проблему с длинными одноцветными строками.

-- Чт сен 06, 2012 09:45:19 --

Для С=8 удалось построить вручную не строго диагональные решения до N=35, для С=7 - до N=27.
Начала строить решения для С=9.
Поскольку эта база данных будет для всех CXNY, начинаю с минимально возможного C9N5:

Изображение

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

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


19/12/10
1546
Pavlovsky
Интересен Ваш метод построения раскраски на основе базовой матрицы с условием:
A+D-B-C <>0 (mod N).

Я приходил к точно такой же матрице при построение попарно-ортогональных прямоугольников.

Поясню на примере решения C6N36.

Чтобы получить это решение достаточно иметь шесть попарно-ортогональных прямоугольников 5х6.
Одним из них возьмём:
Код:
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


Тогда строки всех остальных будут состоять из различных чисел 1..6
Но в столбцах числа могут повторяться.

Будем искать оставшиеся пять прямоугольников, заполняя их строками,
являющимися различными циклическими сдвигами базовой строки:
Код:
1 2 3 4 5 6

(саму эту строку можно взять в качестве первой строки всех прямоугольников, но это не обязательно, главное чтобы все строки были её циклическими сдвигами), например:
Код:
4 5 6 1 2 3
2 3 4 5 6 1
6 1 2 3 4 5
5 6 1 2 3 4
5 6 1 2 3 4


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

Пусть
Код:
A B
C D

некоторый прямоугольник в этой матрице M.

Исходные пять прямоугольников 5х6 будут попарно-ортогональны тогда и только тогда, когда для всех прямоугольников ABCD матрицы M, выполняется условие:
C-A <> D-B (mod 6).
Что совершенно эквивалентно Вашему условию:
A+D-B-C <>0 (mod N).

Подходит, например, матрица:
Код:
6  6  3  5  4
6  5  5  6  2
5  1  6  3  6
2  5  6  5  5
5  3  1  1  5


Из которой получаем следующие пять попарно-ортогональных прямоугольников 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,6,3,5,4,1,
1,1,4,6,5,1,
2,2,5,1,6,1,
3,3,6,2,1,1,
4,4,1,3,2,1,
5,5,2,4,3,1,
6,5,5,6,2,2,
1,6,6,1,3,2,
2,1,1,2,4,2,
3,2,2,3,5,2,
4,3,3,4,6,2,
5,4,4,5,1,2,
5,1,6,3,6,3,
6,2,1,4,1,3,
1,3,2,5,2,3,
2,4,3,6,3,3,
3,5,4,1,4,3,
4,6,5,2,5,3,
2,5,6,5,5,4,
3,6,1,6,6,4,
4,1,2,1,1,4,
5,2,3,2,2,4,
6,3,4,3,3,4,
1,4,5,4,4,4,
5,3,1,1,5,5,
6,4,2,2,6,5,
1,5,3,3,1,5,
2,6,4,4,2,5,
3,1,5,5,3,5,
4,2,6,6,4,5


А из него уже получаем решение C6N36:

(Оффтоп)

Код:
F,F,C,E,D,A,A,A,D,F,E,B,B,B,E,A,F,C,C,C,F,B,A,D,D,D,A,C,B,E,E,E,B,D,C,F,A,A,D,F,E,A,B,B,E,A,F,B,C,C,F,B,A,C,D,D,A,
C,B,D,E,E,B,D,C,E,F,F,C,E,D,F,B,B,E,A,F,A,C,C,F,B,A,B,D,D,A,C,B,C,E,E,B,D,C,D,F,F,C,E,D,E,A,A,D,F,E,F,C,C,F,B,A,A,D,D,A,C,
B,B,E,E,B,D,C,C,F,F,C,E,D,D,A,A,D,F,E,E,B,B,E,A,F,F,D,D,A,C,B,A,E,E,B,D,C,B,F,F,C,E,D,C,A,A,D,F,E,D,B,B,E,A,F,E,C,C,F,B,A,
F,E,E,B,D,C,A,F,F,C,E,D,B,A,A,D,F,E,C,B,B,E,A,F,D,C,C,F,B,A,E,D,D,A,C,B,F,F,E,E,F,B,B,A,F,F,A,C,C,B,A,A,B,D,D,C,B,B,C,E,E,
D,C,C,D,F,F,E,D,D,E,A,A,A,F,F,A,C,B,B,A,A,B,D,C,C,B,B,C,E,D,D,C,C,D,F,E,E,D,D,E,A,F,F,E,E,F,B,A,B,A,A,B,D,B,C,B,B,C,E,C,
D,C,C,D,F,D,E,D,D,E,A,E,F,E,E,F,B,F,A,F,F,A,C,A,C,B,B,C,E,B,D,C,C,D,F,C,E,D,D,E,A,D,F,E,E,F,B,E,A,F,F,A,C,F,B,A,A,B,D,A,D,
C,C,D,F,B,E,D,D,E,A,C,F,E,E,F,B,D,A,F,F,A,C,E,B,A,A,B,D,F,C,B,B,C,E,A,E,D,D,E,A,B,F,E,E,F,B,C,A,F,F,A,C,D,B,A,A,B,D,E,C,B,
B,C,E,F,D,C,C,D,F,A,E,A,F,C,F,C,F,B,A,D,A,D,A,C,B,E,B,E,B,D,C,F,C,F,C,E,D,A,D,A,D,F,E,B,E,B,F,B,A,D,A,C,A,C,B,E,B,D,B,D,C,
F,C,E,C,E,D,A,D,F,D,F,E,B,E,A,E,A,F,C,F,B,A,C,B,E,B,C,B,D,C,F,C,D,C,E,D,A,D,E,D,F,E,B,E,F,E,A,F,C,F,A,F,B,A,D,A,B,B,D,C,F,C,
C,C,E,D,A,D,D,D,F,E,B,E,E,E,A,F,C,F,F,F,B,A,D,A,A,A,C,B,E,B,B,C,E,D,A,D,C,D,F,E,B,E,D,E,A,F,C,F,E,F,B,A,D,A,F,A,C,B,E,B,A,
B,D,C,F,C,B,D,F,E,B,E,C,E,A,F,C,F,D,F,B,A,D,A,E,A,C,B,E,B,F,B,D,C,F,C,A,C,E,D,A,D,B,B,E,F,E,E,D,C,F,A,F,F,E,D,A,B,A,A,F,E,B,
C,B,B,A,F,C,D,C,C,B,A,D,E,D,D,C,C,F,A,F,F,D,D,A,B,A,A,E,E,B,C,B,B,F,F,C,D,C,C,A,A,D,E,D,D,B,B,E,F,E,E,C,D,A,B,A,A,D,E,B,C,
B,B,E,F,C,D,C,C,F,A,D,E,D,D,A,B,E,F,E,E,B,C,F,A,F,F,C,E,B,C,B,B,D,F,C,D,C,C,E,A,D,E,D,D,F,B,E,F,E,E,A,C,F,A,F,F,B,D,A,B,A,A,C,
F,C,D,C,C,D,A,D,E,D,D,E,B,E,F,E,E,F,C,F,A,F,F,A,D,A,B,A,A,B,E,B,C,B,B,C,A,D,E,D,D,D,B,E,F,E,E,E,C,F,A,F,F,F,D,A,B,A,A,A,E,B,C,
B,B,B,F,C,D,C,C,C,E,C,A,A,E,E,F,D,B,B,F,F,A,E,C,C,A,A,B,F,D,D,B,B,C,A,E,E,C,C,D,B,F,F,D,D,F,D,B,B,F,E,A,E,C,C,A,F,B,F,D,D,B,A,
C,A,E,E,C,B,D,B,F,F,D,C,E,C,A,A,E,D,A,E,C,C,A,E,B,F,D,D,B,F,C,A,E,E,C,A,D,B,F,F,D,B,E,C,A,A,E,C,F,D,B,B,F,D,B,F,D,D,B,E,C,A,E,
E,C,F,D,B,F,F,D,A,E,C,A,A,E,B,F,D,B,B,F,C,A,E,C,C,A,D,C,A,E,E,C,E,D,B,F,F,D,F,E,C,A,A,E,A,F,D,B,B,F,B,A,E,C,C,A,C,B,F,D,D,B,D,
D,B,F,F,D,E,E,C,A,A,E,F,F,D,B,B,F,A,A,E,C,C,A,B,B,F,D,D,B,C,C,A,E,E,C,D,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,
D,E,F,A,B,C,D,E,F,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,
C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,E,F,A,B,C,D,E,F,A,
B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E,F,A,B,C,D,E


Хочу отметить, что изоморфными преобразованиями полученный 6-сильный прямоугольник 30х6 можно привести к виду:
Код:
1,1,1,1,1,1,
2,2,2,2,2,1,
3,3,3,3,3,1,
4,4,4,4,4,1,
5,5,5,5,5,1,
6,6,6,6,6,1,
1,6,3,2,5,2,
2,1,4,3,6,2,
3,2,5,4,1,2,
4,3,6,5,2,2,
5,4,1,6,3,2,
6,5,2,1,4,2,
1,3,5,6,4,3,
2,4,6,1,5,3,
3,5,1,2,6,3,
4,6,2,3,1,3,
5,1,3,4,2,3,
6,2,4,5,3,3,
1,4,2,5,6,4,
2,5,3,6,1,4,
3,6,4,1,2,4,
4,1,5,2,3,4,
5,2,6,3,4,4,
6,3,1,4,5,4,
1,5,6,4,3,5,
2,6,1,5,4,5,
3,1,2,6,5,5,
4,2,3,1,6,5,
5,3,4,2,1,5,
6,4,5,3,2,5


Тогда матрица M преобразуется к виду:
Код:
1 1 1 1 1
1 6 3 4 5
1 3 5 2 6
1 2 6 5 4
1 5 4 6 3


То есть мы с самого начала могли искать квази-латинский квадрат 4х4 заполненный числами 2..6 и отвечающий условию:
C-A <> D-B (mod 6).
О чём Вы тоже писали.

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


21/02/10
1594
Екатеринбург
Пользуясь двухмесячным перерывом, планирую систематизировать алгоритмы свои и других участников конкурса. В первую очередь исследовать их эквивалентность. Планирую все алгоритмы привести к единому языку. Свести алгоритмы к операциям над двумя таблицами, условно называемыми таблица сложения и таблица умножения.

Пока в этом направлении сделал элементарные вещи.

Algebraic approach to monochromatic squares
http://infinitesearchspace.dyndns.org/c ... ic-squares

Пусть ячейка таблицы C^2xC^2 имеет номер строки и колонки (s,u). Нумерация строк и колонок начинается с 0. Координаты каждой ячейки запишем 4-мя числами. Тогда s=i*C+j (j<C), u=k*C+l (l<C). Цвет ячейки задается формулой F(s,u)=i*k+j+l. Операции * и + это операции конечного поля из С элементов. Сопряженное решение получается, если использовать F(s,u)=j*l+i+k.

Утверждение. F(s,u)=i*k+j+l эквивалентна построению сильноокрашенного прямоугольника с последующей репликацией по лемме 4.3.

Утверждение. Формулы F(s,u)=i*k+j+l и F(s,u)=j*l+I+k задают эквивалентные квадраты, с точностью до перестановки строк и колонок.

-- Чт сен 06, 2012 12:08:42 --

Quimey Vivas
http://infinitesearchspace.dyndns.org/c ... ic-squares
дал ссылку на Wedderburn's little theorem
http://en.wikipedia.org/wiki/Wedderburn ... le_theorem

Теорема Веддербёрна—Артина

http://mirslovarei.com/content_matenc/v ... -3534.html
теорема, полностью описывающая строение ассоциативных артиновых колец без нильпотентных идеалов; ассоциативное кольцо удовлетворяет условию минимальности для правых идеалов и не имеет нильпотентных идеалов в том и только том случае, если есть прямая сумма конечного числа идеалов, каждый из которых изоморфен полному кольцу матриц конечного порядка над подходящим телом, причем это разложение в прямую сумму единственно с точностью до порядка следования слагаемых. Эта теорема получена первоначально Дж. Вед-дерберном (J. Wedderburn) и доказана в окончательной формулировке Э. Артином [1]. Лит.:[1] Аrtin E., "Bull. Amer. Math. Soc.", 1950, V.56, № 1, p. 65-72. к. А. Жевлаков.

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.09.2012, 10:24 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #615404 писал(а):
Может кто составит компанию по изучению этой теоремы.
Малая теорема Веддербёрна утверждает, что любая конечная область является полем.
Поэтому нет никаких шансов распространить метод двух таблиц (умножения и сложения) на С не являющиеся степенями простых.

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


21/02/10
1594
Екатеринбург
Ну вот сбили на самом взлете. С этой теоремой связаны артиновы и нётеровы кольца. Это тоже тупиковая тема?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.09.2012, 10:53 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #615418 писал(а):
С этой теоремой связаны артиновы и нётеровы кольца.

Область это кольцо без делителей нуля. Именно такие кольца нам и нужны.
К сожалению все такие конечные кольца оказываются полями.

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


21/02/10
1594
Екатеринбург
Есть вот такая гипотеза.
Изображение

В результате получаем таблицу умножения меньше С. Но ведь для построения решения C^2xC^2, достаточно таблицы размером (С-1)х(С-1).

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

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


19/12/10
1546
Pavlovsky
Имхо, более перспективным представляется обобщение Вашего метода основанного на базовой матрице.

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

Пусть
Код:
A B
C D
некоторый прямоугольник в базовой матрице, где A B C D перестановки.

Прямоугольник будет "разрешённым" если перестановка $\mathrm{M}=\mathrm{A}\mathrm{B^{-1}}\mathrm{D}\mathrm{C^{-1}}$ является беспорядочной, то есть не оставляет на месте ни одно число.

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

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


22/03/08

7154
Саратов
Вводим новые рекорды, не стесняемся :D

dimkadimon первый новый рекордсмен и пока единственный (решение C15N198).
Побил рекорд alexBlack :wink:

Напомню, что вводить новые (улучшенные!) результаты могут все, даже те, кто в конкурсе не участвовал.
Открыта база данных конкурса, доступны абсолютно все решения конкурсантов.
Выложены все алгоритмы. Теперь всё намного проще.

А я увлеклась составлением базы данных диагональных решений.
Вчера завершила первую часть базы данных не строго диагональных решений, для С=2,3,...,8. 180 решений!
Интересный момент: не могу никак построить не строго диагональные решения C3N9, C4N16, C5N25, C6N36, C7N49.
Для С=8 нет решений для N>56.

Если у кого-то имеются перечисленные решения, прошу предоставить для базы данных (авторство указывается!).

Могу сообщить хорошую новость: у меня появился соавтор - whitefox.
(базу данных для строго диагональных решений я сделала в соавторстве с Herbert Kociemba).
Вчера whitefox прислал мне свою программу построения диагональных решений.
Его программа строит и строго, и не строго диагональные решения.
Некоторые его строго диагональные решения добавила в базу данных для строго диагональных решений.
Теперь уже я не строю решения вручную :D А вообще-то это было увлекательно, особенно когда надо было подбором ликвидировать возникшие ошибки. Для больших N это получалось не сразу.
Планирую во второй части сделать ещё решения для С=9,10. На этом, пожалуй, остановлюсь.

Надо начинать писать книгу. Очень хочется :roll: Но не знаю, хватит ли сил.

Интересный момент в работе программы whitefox. Начала вчера строить решение C9N14 (до N=13 вручную были построены уже), программа выдаёт мне 5-цветную раскраску! Ничего не понимаю. Спрашиваю автора, почему так. Оказалось, что программа проверяет все цвета по порядку, и в таком маленьком квадрате она управилась 5 цветами :-)
Тогда продолжила построение решений вручную до N=31.
Для N=32 снова пробую по программе, выдаёт 8-цветную раскраску. Ну, заменила одну диагональ на цвет 9. И 8-цветные раскраски выдавались до N=40. Потом стали выдаваться уже 9-цветные.
Да, для каждого С с некоторого N наступает момент, когда программа надолго задумывается.
Для С=9 этот момент наступил при N=58. Начиная с N=32 и до N=57 программа щёлкала решения мгновенно.
У кого есть не строго диагональные решения для N>57 (C=9), выкладывайте, пожалуйста, (или присылайте мне в личку).

Вообще-то до N=72 можно получить решения из строго диагонального решения C9N73 (Herbert Kociemba) путём удаления строк и столбцов, но это будут не оригинальные подобные решения.

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


22/03/08

7154
Саратов
Покажу не строго диагональное решение, которое строит программа whitefox для С=9, N=32:

Изображение

Фактически это 8-цветная раскраска, то есть решение C8N32.
Значит, для данного N программа не дошла до рассмотрения 9-го цвета, вполне управилась восемью цветами :-)

Впрочем, решение C8N32 я легко построила вручную (показано выше). Мне удалось построить вручную решения до C8N35. Дальше продолжила уже по программе, программа быстро построила решения до C8N41, на N=42 надолго задумалась.

Решения для N=42-56 получаю из строго диагонального решения C8N57 (Herbert Kociemba) путём удаления строк и столбцов. Решения эти не оригинальные и однотипные.
Для N>56 нет вообще никаких решений.

-- Пт сен 07, 2012 08:01:40 --

Возвращаясь к матричному методу...
Интересную информацию об этом методе сообщил whitefox (см. выше).

Цитата из статьи alexBlack:

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

0 0 0 0 0 C0
0 1 2 3 4 C1
0 2 4 1 3 C2
0 4 1 5 2 C3
0 5 3 2 1 C4
R0 R1 R2 R3 R4 R5

Некоторые простые замечанию позволяют значительно ускорить перебор таких блоков. Например, переносом столбцов все блоки в первом ряду можно привести к 0, также как и все блоки в первой колонке переносом строк. Во второй строке блоков переносом столбцов блоков можно расставить блоки по неубыванию, также как и во втором столбце. Для C = 10 удается сделать полный перебор. Возможна только матрица 8x8 таких блоков и, соответственно, решение G10|90.

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

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

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


01/06/12
980
Adelaide, Australia
whitefox в сообщении #615438 писал(а):
Pavlovsky
Имхо, более перспективным представляется обобщение Вашего метода основанного на базовой матрице.

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

Пусть
Код:
A B
C D
некоторый прямоугольник в базовой матрице, где A B C D перестановки.

Прямоугольник будет "разрешённым" если перестановка $\mathrm{M}=\mathrm{A}\mathrm{B^{-1}}\mathrm{D}\mathrm{C^{-1}}$ является беспорядочной, то есть не оставляет на месте ни одно число.

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


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

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

ab
cd

где a==(b+k) mod C==(c+m) mod C==(d+k+m) mod C и k,m целые числа. Значит чтобы не было a==(d+2a-c-b)modC. Почти уверен что моё условие равно условию Pavlovsky. Этим методом я даже не смог найти 11х11 C=15, а 13х13 думаю вообще невозможно. На мой взгляд метод не очень перспективный.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 100, 101, 102, 103, 104, 105, 106 ... 130  След.

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



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

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


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

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