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

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

Автор:  Nataly-Mak [ 26 апр 2017, 06:35 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Маленький эксперимент с "браунами"


беру такую комбинацию из 5 пар инверсированных строк

(1,9), (2,4), (3,10), (5,8), (6,7)

Генерирую программой Harry 50000 "браунов", проверяю на ОДЛК. Огромная куча решений, в том числе восьмёрка

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

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

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

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

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

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

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

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

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

Конечно, восьмёрка не уникальная.
На уникальность все решения ещё не проверила, но почти наверняка все не уникальные.
Эх, ну хоть бы одно решеньице уникальное попалось. Тогда можно было бы дальше проверять этих "браунов".

478 миллионов с хвостиком. В каждом миллионе ну очень много решений. Неужели из этого океана решений получается всего 3572 уникальные КФ??? :shock:
Но... всё возможно в этих ОДЛК.

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

Осенила идея проверить "браунов" по НТ.
Взяла набор из 5 инверсированных строк для самого главного "брауна" - основного ДЛК Брауна

(1,7), (2,10), (3,9), (4,6), (5,8)

Генерирую программой Harry все "брауны" с таким набором; да, всё правильно: программа генерирует 1245184 ДЛК.
Проверяю их программой Белышева kanonizator_y на НТ, всего 258 НТ!
Ну, такие порции проверить вполне реально.
Вот только не все "брауны" дают решения от НТ, есть некоторые маскируются, то есть КФ от них совсем не "брауны".
Классический пример - основной ДЛК тройки. Такие решения при проверке по НТ будут потеряны.

Автор:  Nataly-Mak [ 26 апр 2017, 09:31 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

И ещё одна блестящая идея! Использовать новый канонизатор А. Белышева (недавно выложенный на форуме boinc.ru, выше дала ссылку).
Работает быстро. Уже попробовала для порции 1245184 "браунов", примерно 1,5 минуты и - готово.
Найдено 124 тысячи с хвостиком КФ.
Вот эти КФ ещё бы с БД сравнить, но для этого надо БД перевести в новые КФ.

Сейчас что-нибудь попробую.

Автор:  bimol [ 26 апр 2017, 10:04 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Nataly-Mak писал(а):
Вот эти КФ ещё бы с БД сравнить, но для этого надо БД перевести в новые КФ.

Зачем? Достаточно только браунов, а их всего не больше 2 тыс

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

Перевела текущую БД КФ ДЛК не "пустышек" в новые КФ.
44159 новых КФ имеется :)

Теперь вычитаю из 124528 КФ, полученных от главного "брауна", все КФ БД

Имя входного файла ИСТОЧНИК (без расширения):output
Имя входного файла ВЫЧИТАЕМОЕ (без расширения):BD_44159newKF
output.txt
Всего 124528 квадратов (вход) в output.txt
BD_44159newKF.txt
Всего 44159 квадратов (вход) в BD_44159newKF.txt
Уникальных 123301 квадратов (выход).
Для продолжения нажмите любую клавишу . . .

Очень интересно!
Программа говорит, что в БД имеется

[math](124528-123301)=1227[/math] КФ от главного "брауна"

Теперь остаётся проверить 123301 КФ, дадут ли они решения? Жутко любопытно.

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

Nataly-Mak писал(а):
Теперь остаётся проверить 123301 КФ, дадут ли они решения? Жутко любопытно.

Проверила. Все эти КФ "пустышки". В-о-о-о-т!
Отлично! Схема работает.

Итак:
1. выбираем набор из 5 пар инверсированных строк (таких наборов Harry прислал мне 384);
2. генерируем программой Harry для этого набора 1245184 "брауна";
3. канонизируем эти "брауны" новым канонизатором Белышева;
4. вычитаем из полученных КФ все КФ БД не "пустышек";
5. проверяем на ОДЛК оставшиеся КФ.

Если Harry правильно посчитал, таких порций по 1245184 "брауна" будет всего 384.
Проверить все вполне реально.
Главного "брауна" я уже проверила. Осталось всего 383 порции проверить по данной схеме :)

Автор:  Nataly-Mak [ 26 апр 2017, 11:35 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Чего-то я, похоже, не понимаю.
Начала проверять с другим набором из 5 инверсированных строк.
Всё то же самое: сгенерировалось 1245184 "брауна", канонизатор выдаёт

Загружена хеш-таблица
Время загрузки: 0.015 сек

Введено ДЛК: 1245184
Время загрузки: 59.452 сек

Найдено КФ: 124528
Время поиска: 7.317 сек

КФ записаны в файл output.txt
Время записи: 12.807 сек

Общее время работы: 79.606 сек

Для выхода нажмите ENTER:

Найдено 124528 КФ.
Вычитаю КФ БД, остаётся 123301 уникальных КФ.
И не только количества одинаковые, сами КФ тоже одинаковые.

"Брауны" не зависят от набора 5 пар инверсированных строк??? :shock:
Или это просто случайно совпало?
Сейчас проверю для третьего набора 5 пар инверсированных строк.

Автор:  Nataly-Mak [ 26 апр 2017, 11:52 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Беру самый первый набор 5 инверсированных строк из списка Harry

(1,2) (3,4) (5,7) (6,9) (8,10)

Генерирую "брауны", их получается опять 1245184.
И дальше всё по схеме. И всё совпадает! Все КФ одинаковые.
Ну и дела.

Тогда сейчас возьму 1227 КФ, которые вычитает БД из 124528 КФ, и проверю их все на ОДЛК. Посмотрю, сколько они дадут уникальных КФ. Должно быть 3572 уникальные КФ от них получено.

Кстати, Harry пишет, что у него тоже от любого набора из 5 инверсированных строк генерируется 1245184 "брауна".

Автор:  bimol [ 26 апр 2017, 11:55 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

На boinc.ru выложили
[math]50 000[/math] КФ ОДЛК !!!

http://forum.boinc.ru/default.aspx?g=posts&m=87518#post87518

Автор:  Nataly-Mak [ 26 апр 2017, 12:21 ]
Заголовок сообщения:  Re: Ортогональные латинские квадраты 10-го порядка

Чем дальше, тем интереснее :)
Пропустила один раз эти 1227 КФ через программу svb проверки на ОДЛК, посмотрела решения, две восьмёрки есть, шесть шестёрок есть, двушки и четвёрки есть (количесвтва не считала), а вот тройки и однушек нету!
И дали все эти решения 2567 уникальных КФ.
Тэк-с,
[math]3572-2567=1005[/math] уникальных КФ не хватает.

Значит, надо второй раз пропустить полученные 2567 КФ через программу проверки на ОДЛК.

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