Математический форум 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/