| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Ортогональные латинские квадраты 10-го порядка http://mathhelpplanet.com/viewtopic.php?f=57&t=46638 |
Страница 39 из 421 |
| Автор: | bimol [ 27 фев 2016, 22:03 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Другой вариант выбора элемента на k-строке: заполняем массив 10 единичками, если цифра уже есть в трансверсали, то на ее месте ставим 0 идем по к строке - смотрим по массиву незанятость цифры, - здесь надо удостовериться еще что цифры сверху не входят в трансверсаль Возможно это быстрее, но раз начал перебирать цифры по возрастанию, то и продолжил. В данном случаи считается быстро и стоит шлифовать. |
|
| Автор: | ivashenko [ 27 фев 2016, 22:05 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Значит нужно учиться находить ортогональный соквадрат, а не перебирать. |
|
| Автор: | ivashenko [ 27 фев 2016, 22:10 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
bimol писал(а): Другой вариант выбора элемента на k-строке: Хрен редьки не слаще. |
|
| Автор: | bimol [ 27 фев 2016, 22:12 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko писал(а): Каждой ячейке массива-маски присвоен счетчик, при попадании в ячейку элемента из трансверсали счетчик прибавляет 1, бросаем последовательно 10 трансверсалей на массив- маску, если какой-либо из счетчиков увеличился на 2, отбрасываем рассматриваемую комбинацию и переходим к следующей. разрешенные значения для этих 100 счетчиков 0 и 1. Маска - квадратная матрица. Как бросаем 10 трансверсалей на массив- маску, куда что попадает? Сколько операций это займет?
|
|
| Автор: | Nataly-Mak [ 27 фев 2016, 22:15 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Раскрасила 10 непересекающихся транверсалей в исходном ЛК из книги Кнута ![]() Всё работает и для ДЛК и для обычных ЛК. Прогрммка Алексея 10 непересекающихся трансверсалей по ортогональной паре квадратов находит. |
|
| Автор: | bimol [ 27 фев 2016, 22:18 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko писал(а): Значит нужно учиться находить ортогональный соквадрат, а не перебирать. Кнут в руки и в вперед.ivashenko писал(а): Хрен редьки не слаще. Быстрее.
|
|
| Автор: | Nataly-Mak [ 27 фев 2016, 22:22 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko писал(а): Хрен редьки не слаще. Что можете предложить слаще? |
|
| Автор: | ivashenko [ 27 фев 2016, 22:27 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
bimol писал(а): ivashenko писал(а): Каждой ячейке массива-маски присвоен счетчик, при попадании в ячейку элемента из трансверсали счетчик прибавляет 1, бросаем последовательно 10 трансверсалей на массив- маску, если какой-либо из счетчиков увеличился на 2, отбрасываем рассматриваемую комбинацию и переходим к следующей. разрешенные значения для этих 100 счетчиков 0 и 1. Маска - квадратная матрица. Как бросаем 10 трансверсалей на массив- маску, куда что попадает? Сколько операций это займет?Бросаем элементы трансверсалей так, как они были расположены в квадрате. Т.е. патаемся из них создать квадрат. На один квадрат уйдет от 20 до 200 операций. И нужно будет перебрать таких квадратов от 1 до 10^23. Это как повезет. Если кроме 10 непересекающихся трансверсалей больше нет множеств меньшей мощности из непересекающихся трансверсалий, то на один квадрат будет уходить 10-20 операций. Но множества из непересекающихся трансверсалий скорее всего есть. В любом случае перебор- это дело гиблое. |
|
| Автор: | ivashenko [ 27 фев 2016, 22:41 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Nataly-Mak писал(а): Паркер нашёл ортогональную пару методом Эйлера за один час. Это Вы всё перепутали. |
|
| Автор: | bimol [ 27 фев 2016, 22:43 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko писал(а): Бросаем элементы трансверсалей так, как они были расположены в квадрате. Т.е. патаемся из них создать квадрат. На один квадрат уйдет от 20 до 200 операций. Плюс 100, получается 120-300.С этим более или менее уточнили.Цитата: И нужно будет перебрать таких квадратов от 1 до 10^23. Оценка в 808*807*806...800*799/10! неправильная. Трансверсали начинающие с одинаковой цифры не могут входить в десятку Цитата: Это как повезет. Если кроме 10 непересекающихся трансверсалей больше нет множеств меньшей мощности из непересекающихся трансверсалий, то на один квадрат будет уходить 10-20 операций. Но множества из непересекающихся трансверсалий скорее всего есть. В любом случае перебор- это дело гиблое. Этот поток сознания не осилил.
|
|
| Страница 39 из 421 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|