Задача о циклических блоках

Message boards : Science : Задача о циклических блоках
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3115 - Posted: 21 Oct 2021, 19:24:36 UTC
Last modified: 23 Oct 2021, 22:57:16 UTC

Репост с форума Math Help Planet
http://mathhelpplanet.com/viewtopic.php?f=48&t=75313

О циклических блоках в ДЛК (диагональном латинском квадрате) вы можете посмотреть в статье OEIS https://oeis.org/A307166
В этой статье они называются циклами, я называю их циклическими блоками.

У меня довольно сложная задача о циклических блоках.
Дан конкретный ДЛК 12-го порядка (у меня тысячи таких ДЛК).
Требуется написать программу, которая
1) найдёт в заданном ДЛК все циклические блоки;
2) сделает всевозможные преобразования этих блоков и выдаст все получившиеся в результате этих преобразований ДЛК.

Покажу иллюстрацию, это я нашла визуально циклические блоки (независимые) в заданном ДЛК 12-го порядка



Независимый блок – это такой блок, который не пересекается с другими блоками.
Вы можете без труда найти визуально в этом ДЛК несколько зависимых блоков.
В ДЛК красным цветом изначально были раскрашены диагонали, это для того, чтобы было видно, как циклические блоки наезжают на диагонали.
На показанной иллюстрации они удачно наезжают: преобразование таких блоков не нарушит диагональности квадрата.

Осталось сказать, как преобразовывается циклический блок. Это очень просто: в исходном циклическом блоке числа взаимозаменяются.
То есть если циклический блок составлен из чисел 2, 7, надо заменить в нём все 2 на 7, а все 7 на 2.
Таким образом, каждый циклический блок имеет два состояния: исходное и обращённое.
Независимые блоки можно преобразовывать в любых комбинациях. С пересекающимися (зависимыми) блоками сложнее.

Как уже сказано, циклические блоки я ищу визуально, это просто. А вот заставить программу искать такие блоки что-то не получается.
Для преобразования найденных визуально блоков программку написала, она работает.
Но! Без программной реализации первого пункта (поиск блоков) – никуда.
Прошу помочь с этой реализацией, что-то у меня с этим полный туман :(

И ещё один нюанс: не используются полные циклические блоки (полный цикл, то есть, например, блок {k,m} содержит все 12 чисел k и все 12 чисел m).
Такие циклические блоки тоже встречаются.

PS. Иллюстрация тут, к сожалению, не отображается.
Сейчас я её загружу на Яндекс.Диск.

Готово!
Здесь иллюстрация
https://disk.yandex.ru/i/9KxuTjg0ElNy5A

PS. После установки нового сертификата на своём компьютере загрузила иллюстрацию на хостинг postimages.org.
Теперь иллюстрация показывается.
ID: 3115 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3116 - Posted: 21 Oct 2021, 19:46:43 UTC

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

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

Предлагаю всем попробовать написать такую программу.
ID: 3116 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3120 - Posted: 24 Oct 2021, 1:17:34 UTC
Last modified: 24 Oct 2021, 1:56:47 UTC

Тема на форуме Math Help Planet уже закрыта (сразу же!).
Это такие санкции против меня :)
Санкции - это сейчас очень модно.
Только... я не видела ни на одном форуме таких дебильных санкций.
Если пользователь проштрафился, санкции бывают: либо временный бан, либо постоянный бан.
Но чтобы закрывать все темы... чтобы переносить в Мусор все сообщения пользователя в других темах... чтобы изменять ссылки в сообщениях пользователя на ссылку "базарная баба"... - таких санкций я не встречала НИГДЕ.
Ну, санкции вполне по модератору, по Сеньке и шапка :)
Ладно, может быть, скоро выдадут, наконец, бан.
Получить бан на форуме, где правит бал глупый модератор (единственный, зато ВЕРХОВНЫЙ) - это не наказание, а награда!
Жду награждения - заслуженного!

Цитата (чтобы не быть голословной) отсюда
https://boinc.progger.info/odlk/forum_thread.php?id=21&postid=7398
И ещё один скриншот, это другая тема "Архивирование-2", которую Верховный модератор отправила в Мусор.
В этой теме была произведена точно такая же замена ссылки


Мной была указана следующая ссылка по теме
https://boinc.progger.info/odlk/forum_thread.php?id=146&postid=7387

Покажу изменённую ссылку чётко
https://ru.wiktionary.org/wiki/%D0%B1%D0%B0%D0%B7%D0%B0%D1%80%D0%BD%D0%B0%D1%8F_%D0%B1%D0%B0%D0%B1%D0%B0
Посмотрите, куда она ведёт.

Оригинальная санкция, не правда ли?
При этом, заметьте: модератор изменяет ссылку, не оставляя никаких пометок об этом.
Это грубейшее нарушение в действиях модератора.

А теперь к делу.
Господа, регистрация на этом сайте свободная.
Вы можете свободно участвовать в обсуждении этой задачи, и не только этой!
Приходите!
Мне очень нужна помощь хорошего программиста. У меня куча алгоритмов, самых разных.
Не все из них я сама могу реализовать программно.
Есть у меня отличный помощник в Канаде - Harry White.
Ну, а Россия что же? Не имеет хороших программистов? Или они есть, но помогать мне не желают? :(
ID: 3120 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3121 - Posted: 24 Oct 2021, 5:09:21 UTC
Last modified: 24 Oct 2021, 5:12:06 UTC

Господа!
Замечу попутно: почти все мои темы открыты для обсуждения.
Если вы занимаетесь латинскими квадратами и хотите что-то добавить к моим сообщениям, или что-то непонятное вам спросить, - пожалуйста!
Вы можете писать по-русски и по-английски.
На вопросы, заданные по-английски, я постараюсь ответить по-английски.

Однако прошу не писать сообщений, не относящихся к теме.
Оффтоп здесь удаляется либо скрывается.
ID: 3121 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3206 - Posted: 26 Nov 2021, 2:11:08 UTC
Last modified: 26 Nov 2021, 2:12:35 UTC

Мы с форумчанином с форума Math Help Planet немного поработали с циклическими блоками.
Смотрите тему
http://mathhelpplanet.com/viewtopic.php?f=63&t=75775

Однако вариант программы для всех циклических блоков в заданном ДЛК (независимых и пересекающихся) работает очень долго.

Например, сейчас запустила эту программу для своего квадрозавра, вот этого (28496 Д-трансверсалей)

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

В этом ДЛК программа нашла 56 уникальных циклических блоков: независимых и пересекающихся.
При этом независимых циклических блоков (первый вариант программы) найдено всего 8, то есть это максимальное количество независимых циклических блоков в данном ДЛК.

Показываю консоль

Найдено блоков: 56
 Возможно  вариантов: 72057594037927936
 Вариантов проверено: 4153332106
 Преобразовано: 18240
 Создано файлов: 1

 Старт: 2021-11-26T05:34:12

 автор: Захар Пехтерев

Ну, это будет месяц преобразовываться :)
Никуда не годится!
Я написала в указанной теме на форуме MHP, что второй вариант программы требует оптимизации с целью ускорения.

Хорошо, что хотя бы при прерывании программы уже найденные преобразованные ДЛК сохраняются.
Можно покрутить немного, потом прервать и проверить найденные ДЛК.
ID: 3206 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3207 - Posted: 26 Nov 2021, 8:32:16 UTC
Last modified: 26 Nov 2021, 9:15:04 UTC

Черепашка трудится 7 часов.
Результат на данный момент

 Найдено блоков: 56
 Возможно  вариантов: 72057594037927936
 Вариантов проверено: 114955521879
 Преобразовано: 80503
 Создано файлов: 1

 Старт: 2021-11-26T05:34:12

Выход преобразованных ДЛК что-то не очень, при том, что циклических блоков в ДЛК много.
Интересно, что даст этот квадрозавр по данному алгоритму (преобразование циклических блоков). Конечно, нужны новые элементы спектра. Будут ли они?
Хотя полный результат получить не удастся, потому что выполнить программу до конца нереально на моём компьютере.
Покручу ещё немного, может, хотя бы 100000 преобразованных ДЛК наберётся.

Прервала. Есть одинаковые ДЛК, но мало. Зато очень много изоморфных ДЛК.
Удалила дубликаты, канонизировала и запустила КФ ДЛК на обсчёт Д-трансверсалей.
КФ ДЛК получилось 6000 с хвостиком.
Жду результат.

Увы! Новых элементов спектра не найдено.
ID: 3207 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3210 - Posted: 27 Nov 2021, 0:29:51 UTC

Для Захара

Ошибки вылезают в обоих вариантах программы.
Подозреваю, что ошибка вылезает, когда в ДЛК найдено 0 циклических блоков.
ID: 3210 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3221 - Posted: 3 Dec 2021, 6:51:05 UTC

Решила попробовать преобразование циклических блоков в новом квадрозавре с 30192 Д-трансверсалями

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

Программа Захара нашла в этом ДЛК 36 уникальных циклических блоков.
У меня было такое же количество циклических блоков в антиквадрозаврике со 115 Д-трансверсалями.
Программа работала больше 4 часов.
Запустила программу, вычисления начались.
ID: 3221 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 3083
Credit: 0
RAC: 0
Message 3222 - Posted: 3 Dec 2021, 11:44:31 UTC
Last modified: 3 Dec 2021, 14:17:49 UTC

Ну вот, черепашка отстрелялась



Почти 5 часов работала программа.
Сейчас буду проверять найденные ДЛК, их 146989 штук.
Среди преобразованных ДЛК (при преобразовании циклических блоков), как правило, очень много изоморфных.

После удаления дубликатов (их было 36 штук, кстати, ровно по количеству циклических блоков) и канонизации получилось всего 1267 КФ ДЛК.
Н-и-ч-е-г-о нового не найдено по Д-трансверсалям.
Увы, пока этот алгоритм плохо работает. Очень долгое преобразование циклических блоков (в одном ДЛК!), а в итоге ноль результатов.
ID: 3222 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : Science : Задача о циклических блоках


©2024 Progger & Stefano Tognon (ice00)