Математический форум Math Help Planet
http://mathhelpplanet.com/

Ортогональные латинские квадраты 10-го порядка
http://mathhelpplanet.com/viewtopic.php?f=57&t=46638
Страница 48 из 421

Автор:  Nataly-Mak [ 29 фев 2016, 07:24 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

svb
опробовала вашу программу. Класс!
Ввела в качестве исходного ДЛК Брауна (в первоначальном виде).
Программа выдала 5504 трансверсалей.
М-н-о-о-о-г-о-о :)

Теперь надо научиться выбирать в этом массиве наборы по 10 непересекающихся трансверсалей.
Если эту операцию удастся выполнять так же быстро, как поиск всех трансверсалей, будет здорово.
Алгоритм поиска пары ОДЛК по заданному ДЛК будет реализован!

А. Белышев пишет, что у Кнута всё подробно расписано, как из 808 трансверсалей выбрать 10 неперескающихся.
Осилим? :)

Небольшое замечание по программе: программа запрашивает имя входного файла, вводим, жмём Enter. Всё хорошо.
Программа квадрат из файла ввела и вывела его на экран.
После этого программа опять ждёт, чтобы нажали Enter.
А зачем второй раз нажимать Enter? Не поняла.
Хорошо, что я описание прочитала и нажала второй раз Enter, а то сидела бы и ждала долго-долго...

Автор:  Nataly-Mak [ 29 фев 2016, 07:36 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Проверила программу svb для ЛК Паркера из книги Кнута.
Программа нашла 808 трансверсалей

Изображение

Результат выдаётся мгновенно!

Автор:  Nataly-Mak [ 29 фев 2016, 07:41 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Avgust
для вашего квадратика программа нашла 4224 трансверсали, поменьше, чем для ДЛК Брауна, но вполне достаточно, чтобы среди них оказался нужный набор из 10 неперескающихся трансверсалей.

Теперь вам задачка прямо в лоб :)
Все трансверсали для вашего ДЛК найдите по программе svb. Это одно мгновение.
А потом среди этих трансверсалей ищите 10 неперескающихся. Как найдёте, так новая пара ОДЛК будет построена - для преобразованного квадрата Брауна.

Можете написать программу для выбора из заданного массива n трансверсалей 10 неперекающихся?

Автор:  Nataly-Mak [ 29 фев 2016, 07:51 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Для ДЛК, построенного методом Гергели,

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

программа нашла 2816 трансверсалей.

Вот хороший пример для тестирования следующей программы - выбора комплекта из 10 непересекающихся трансверсалей.
Форумчанин на форуме boinc.ru проверил этот квадрат и написал, что у него нет ортогонального соквадрата.
Это значит, что среди всех 2816 трансверсалей нет 10 непересекающихся.

Автор:  Nataly-Mak [ 29 фев 2016, 08:16 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Вот ещё пример для тестирования - пара ОДЛК, найденная в проекте SAT@home

ДЛК №1

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

ДЛК №2

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

Для ДЛК №1 программа svb выдала 820 трансверсалей.
(Близко к количеству трансверсалей в ЛК Паркера.)

Набор из 10 непересекающихся трансверсалей я нашла по программе А. Белышева:

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

Как утверждают ребята с проекта, у ДЛК №1 только один ортогональный соквадрат, значит, комплект из 10 непересекающихся трансверсалей только один. Вот надо его выбрать из 820 известных трансверсалей.

Замечание: в программке А. Белышева в качестве исходного введён ДЛК №2, а в качестве ортогонального соквадрата - ДЛК №1.

#include <iostream>

using namespace std;

int sokvadrat[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{2,4,9,7,0,3,5,1,6,8},
{9,7,1,5,6,4,8,3,0,2},
{1,0,8,6,9,2,7,4,5,3},
{8,6,5,0,7,1,3,2,9,4},
{6,3,4,9,2,8,0,5,1,7},
{5,9,7,8,3,0,2,6,4,1},
{3,8,0,4,5,7,1,9,2,6},
{7,5,6,2,1,9,4,8,3,0},
{4,2,3,1,8,6,9,0,7,5}};

int ishodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{4,9,1,5,6,0,2,8,7,3},
{2,0,7,8,9,1,5,4,3,6},
{5,2,9,4,8,3,1,6,0,7},
{7,5,4,1,3,2,9,0,6,8},
{1,8,0,7,5,6,4,3,9,2},
{9,3,6,0,1,7,8,2,5,4},
{6,4,8,2,7,9,3,5,1,0},
{8,6,3,9,0,4,7,1,2,5},
{3,7,5,6,2,8,0,9,4,1}};

int otvet[10][10];

int main(){
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
otvet[sokvadrat[i][j]][i] = ishodn[i][j];
}
}
cout << endl;
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
cout << otvet[i][j] << (j != 9 ? ' ' : '\n');
}
}
cout << endl;
}


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

P. S. А для ДЛК №2 программа svb нашла 840 трансверсалей.

Автор:  Nataly-Mak [ 29 фев 2016, 08:37 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Кстати, об ортогональных соквадратах для каждого из ДЛК известной пары.
Вот есть пара ОДЛК Брауна:

ДЛК №1

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

ДЛК №2

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

ДЛК №1 имеет только одного ортогонального собрата (это показанный тут ДЛК №2).

А вот ДЛК №2 (знаменитый квадрат Брауна) имеет аж 4 ортогональных соквадрата!

Поэтому надо проверять оба ДЛК в известной паре ОДЛК.

Автор:  svb [ 29 фев 2016, 09:53 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Программа для поиска ортогональных квадратов с исходником на паскале
Lat02
Lat02.exe - программа для поиска трансверсалей и ортогональных квадратов
латинского квадрата со стороной 10.

a41.txt, q1.txt - примеры исходных латинских квадратов.

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

Создается файл:
trans.txt - набор трансверсалей для исходного квадрата.

Трансверсаль h[0],h[1],...,h[9] - это набор ячеек квадрата с координатами
[0,h[0]],[1,h[1]],...,[9,h[9]]

После этого начинается поиск ортогональных квадратов,
ort.txt - ортогональные квадраты.

Примечание.
Квадрат q1.txt взят из книги:
Кнут Д. Искусство программирования. Том 4А.
Для этого квадрата находится только один ортогональный квадрат.

Для квадрата A41.txt квадратов очень много, поэтому пришлось ввести
ограничение на максимальное число выводимых квадратов.
Кроме этого, в начало файла ort.txt записывается строка со значением
номера начальной трансверсали блока 0, с которой начинается перебор.
Новое значение этого номера можно записать в файл lat.ini, тогда
программа начнет работать с этого номера.

Автор:  Nataly-Mak [ 29 фев 2016, 10:17 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

svb писал(а):
Программа для поиска ортогональных квадратов с исходником на паскале
Lat02

Высший пилотаж! :Bravo:
Ввела ДЛК Брауна и max=5, программа выдала 5 ортогональных квадратов.
Я даже испугалась сначала - откуда 5, когда должно быть всего 4?
Посмотрела на квадраты, а они... не диагональные. То есть программа ищет все ортогонгальные соквадраты для заданного - и диагональные, и не диагональные. Класс!
И для ДЛК Гергели нашла 2 обычных ортогональных ЛК, и для квадрата, который Avgust изобрёл тоже нашла обычные ортогональные ЛК - 2 шт.

Теперь осталось совсем немного - выбирать из всего множества построенных ортогональных ЛК диагональные, потому что у нас задача: строить пары ОДЛК (ортогональных диагональных латинских квадратов).

svb
наверное, можно, вашей программе дать такое задание: строить только диагональные ортогональные ЛК.
Сделать вариант программы для ДЛК.

Автор:  Nataly-Mak [ 29 фев 2016, 10:23 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Ах, да...
теперь можно приступать к решению задачи века :)
найти тройку попарно ортогональных ЛК 10-го порядка.
Программа выдаёт для заданного ЛК целую кучу ортогональных соквадратов. Но вот... взаимно ортогональных среди них не находится. А вдруг и найдутся.

Автор:  Avgust [ 29 фев 2016, 10:25 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak, то, что в подправленном квадрате Брауна 4224 трансверсалей (число палиндромное! ) - для меня полная неожиданность. Это же жутко много. Проги svb у меня нет, увы, самому писать долго будет. Гораздо проще это сделать Вам. Ведь только пару раз Enter нажать. :)

Страница 48 из 421 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/