| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Ортогональные латинские квадраты 10-го порядка http://mathhelpplanet.com/viewtopic.php?f=57&t=46638 |
Страница 44 из 421 |
| Автор: | Nataly-Mak [ 28 фев 2016, 09:58 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Может быть, подключатся вновь прибывшие силы
|
|
| Автор: | Nataly-Mak [ 28 фев 2016, 10:39 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Эксперимент с неправильными трансверсалями Продолжила свой эксперимент, 8 непересекающихся трансверсалей в ДЛК Брауна нашла вручную, осталось найти ещё две, не получилось. Получились только неправильные транверсали - в них есть повторяющееся число. Но... все 10 трансверсалей непересекающиеся! 1) 0 1 2 3 4 5 6 7 8 9 2) 2 4 0 7 1 6 5 3 9 8 3) 8 7 9 0 3 1 4 2 5 6 4) 7 6 3 1 5 8 9 4 2 0 5) 3 5 7 4 6 9 8 1 0 2 6) 9 3 8 2 7 4 1 0 6 5 7) 5 2 6 9 0 7 3 8 1 4 8) 6 0 5 8 2 3 7 9 4 1 9) 4 8 1 6 8 2 0 5 3 7 (неправильная, число 8 повторяется) 10) 1 9 4 5 9 0 2 6 7 3 (неправильная, число 9 повторяется) Картинка с этими раскрашенными трансверсалями ![]() Очень интересно. Ещё большие чудеса дальше. По этому раскрашенному квадрату с двумя неправильнями транверсалями строю ЛК. Он построился! Только: 1. он не диагональный; 2. он не ортогонален исходному ДЛК, ортогональности нет только в двух ячейках из 100. Вот он - этот ЛК: 0 1 2 3 4 5 6 7 8 9 Любопытный получился квадратик. Каждая строка в нём перевёрнута (отзеркалена). |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 10:55 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
И в завершение всех чудес --- ввожу в программку Алексея исходный ДЛК Брауна и построенный мной ЛК, прогпраммка выдаёт те же самые 10 непересекающихся трансверсалей, которые найдены у меня (две из них неправильные). Код программки ▼
Выданные программой трансверсали 0 1 2 3 4 5 6 7 8 9 Сравните с найденными мной: 1) 0 1 2 3 4 5 6 7 8 9 2) 2 4 0 7 1 6 5 3 9 8 3) 8 7 9 0 3 1 4 2 5 6 4) 7 6 3 1 5 8 9 4 2 0 5) 3 5 7 4 6 9 8 1 0 2 6) 9 3 8 2 7 4 1 0 6 5 7) 5 2 6 9 0 7 3 8 1 4 8) 6 0 5 8 2 3 7 9 4 1 9) 4 8 1 6 8 2 0 5 3 7 (неправильная, число 8 повторяется) 10) 1 9 4 5 9 0 2 6 7 3 (неправильная, число 9 повторяется) Те же самые, только переставлены. |
|
| Автор: | ivashenko [ 28 фев 2016, 13:29 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Есть идея: Предположим у нас есть множество всех трансверсалей, тогда 1. Строим квадрат 10*10 ячейки которого будут представлять собой массивы трансверсалей. Столбцы нумеруем индексами i, строки j, принимающими значения 0-9. 2. Сортируем все 808 трансверсалий по первому разряду: В первом разряде 0- помещаем в ячейку 00, в первом разряде 1- помещаем в ячейку 01, в первом разряде 2- в ячейку 02, т.е. в третью ячейку первого столбца. И т.д., пока не рассортируем все трансверсали по ячейкам первого столбца. 3. Вновь берем все 808 трансверсалей и сортируем их по 0: 0 в первом разряде- уже помещены в ячейку 00, 0 во втором разряде помещаем в ячейку 10, 0 в третьем разряде- в ячейку 20, ..., 0 в 10 разряде - в ячейку 90. 4. На пересечении строк и столбцов ij записываем пересечение множеств, стоящих в ячейках i1 и 1j. 5. Вычитаем пересечения из множества всех трансверсалей. 6. Вновь сортируем оставшиеся трансверсали, но уже по второму разряду:во втором разряде 1 - в ячейку 00, во втором разряде 2- в ячейку 01, во втором разряде 3 - в ячейку 02 ...., во втором разряде 00- в ячейку 09. пока не рассортируем все трансверсали по первому столбцу. 7. Вновь берем множество трансверсалей, которое сортировали в предыдущем пункте и сортируем его по 1: в первом разряде 1 - в ячейку 00, во втором разряде 1 - в ячейку 10, в третьем разряде 1 - в ячейку 20,...... 8. На пересечении строк и столбцов ij записываем пересечение множеств, стоящих в ячейках i1 b 1j. 9. Вычитаем пересечения из исходного множества, которое сортировали в пунктах 6,7. 10. Повторяем пункты 6-9 10 раз, пока не удалим из множества трансверсалей все пересечения. Возможно что-то подобное и придумал Эйлер. Это действительно очень похоже на метод кругов Эйлера. |
|
| Автор: | Avgust [ 28 фев 2016, 13:39 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
А Почему нет написанных статей о том, что придумал Эйлер? |
|
| Автор: | ivashenko [ 28 фев 2016, 13:53 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Они скорее всего есть, просто либо в англоязычном сегменте интернет, либо не столь известны в широких кругах, поскольку вопрос очень узкоспециализированный. |
|
| Автор: | Avgust [ 28 фев 2016, 15:20 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko Вопрос как раз классный! Нужно хоть на английском, хоть на арабском, но найти метод. Зачем повторять путь гения? |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 19:16 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Avgust писал(а): ivashenko Вопрос как раз классный! Нужно хоть на английском, хоть на арабском, но найти метод. Зачем повторять путь гения? Avgust Эйлер не писал программ. Алгоритм рассказали, разжевали, осталось проглотить. По поводу программной реализации... svb выложил ссылку на книгу Кнута на русском. Там, как мне пишут, всё расписано и прописано до мелочей. Как искать эти 808 трансверсалей и как из них выбирать 10 неперескающихся. Алгоритм "танцующих связей", вот Алексей мне подсказывает. Но я без понятия, что это за алгоритм. Попробую разобраться. Но это долго будет
|
|
| Автор: | bimol [ 28 фев 2016, 19:37 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Avgust писал(а): Зачем повторять путь гения? Я пожалуй покумекую еще пару дней. Последую методе ivashenko. Конечно не просеку, но зато при изучении будет понятно глубина вопроса. Набью шишки, так сказать.
|
|
| Автор: | ivashenko [ 28 фев 2016, 19:47 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko писал(а): Есть идея: Предположим у нас есть множество всех трансверсалей, тогда 1. Строим квадрат 10*10 ячейки которого будут представлять собой массивы трансверсалей. Столбцы нумеруем индексами i, строки j, принимающими значения 0-9. 2. Сортируем все 808 трансверсалий по первому разряду: В первом разряде 0- помещаем в ячейку 00, в первом разряде 1- помещаем в ячейку 01, в первом разряде 2- в ячейку 02, т.е. в третью ячейку первого столбца. И т.д., пока не рассортируем все трансверсали по ячейкам первого столбца. 3. Вновь берем все 808 трансверсалей и сортируем их по 0: 0 в первом разряде- уже помещены в ячейку 00, 0 во втором разряде помещаем в ячейку 10, 0 в третьем разряде- в ячейку 20, ..., 0 в 10 разряде - в ячейку 90. 4. На пересечении строк и столбцов ij записываем пересечение множеств, стоящих в ячейках i1 и 1j. 5. Вычитаем пересечения из множества всех трансверсалей. 6. Вновь сортируем оставшиеся трансверсали, но уже по второму разряду:во втором разряде 1 - в ячейку 00, во втором разряде 2- в ячейку 01, во втором разряде 3 - в ячейку 02 ...., во втором разряде 00- в ячейку 09. пока не рассортируем все трансверсали по первому столбцу. 7. Вновь берем множество трансверсалей, которое сортировали в предыдущем пункте и сортируем его по 1: в первом разряде 1 - в ячейку 00, во втором разряде 1 - в ячейку 10, в третьем разряде 1 - в ячейку 20,...... 8. На пересечении строк и столбцов ij записываем пересечение множеств, стоящих в ячейках i1 b 1j. 9. Вычитаем пересечения из исходного множества, которое сортировали в пунктах 6,7. 10. Повторяем пункты 6-9 10 раз, пока не удалим из множества трансверсалей все пересечения. Возможно что-то подобное и придумал Эйлер. Это действительно очень похоже на метод кругов Эйлера. Попробовал проверить это на ОЛК 4-го порядка- не действует, ерунда какая-то получается. Попробую всё перепроверить. |
|
| Страница 44 из 421 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|