|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Kruglov 2:5015/70.5 09 May 2002 20:32:08
To : Andrew Plyako
Subject : Простенькая задача
--------------------------------------------------------------------------------
Вторник 07 Мая 2002 22:44, Andrew Plyako wrote to All:
AP> Есть матрица (двумерный массив) n на n. Hадо в цикле перебрать все
AP> варианты расстановки 0 и 1 в этой матрице; все варианты __с точностью
AP> до отражений/поворотов__.
AP> Какой алгоритм можно предложить? Просто промоделировать все 2^{n^2}
AP> вариантов расстановки 0 и 1 несложно. Hо как при этом "пропустить" уже
AP> полученные (с точностью до поворота) варианты?
Это, кстати, сократит количество вариантов менее, чем в 8 раз, т.е. их будет
больше 2^{n^2-3}.
Теперь решение.
Обозначим поворот (например, прочив часовой стрелки) на 90 градусов S,
отражение (например, относительно вертикальной прямой) R. <a,b> -- группа,
сожержащая все произведения, составленные a и b в любом порядке (и только их).
Можно разбить матрицу на восьмерки и четверки (и при нечетном n будет еще
центральный элемент), которые преобразуются при поворотах и отражениях
независимо. Центральный элемент можно перебирать отдельно, например, самым
внутренним циклом, т.к. его S и R не меняют. Матрицу будем представлять в виде
вектора из всех ее восьмерок и четверок: M=(x_1,...,x_m).
Будем перебирать матрицы M, для которых m<=fM для всех f\in <S,R>. Порядок на M
лексикографический, порядок на 8-ках и 4-ках любой (линейный :). Перебирать
тоже будем в этом же порядке.
Пусть начало M_{k-1}=(x_1,...,x_{k-1}) такое, что M_{k-1}<=fM_{k-1} для f\in
<S,R>, уже подобрано. Hадо перебрать все начала длины k с тем же свойством,
начинающиеся с M_{k-1}. Пусть G(x) -- подгруппа <S,R>, эл-ты которой переводят
x в себя, G_{k-1}=G(M_{k-1}).
M_k<=fM_k <=> (M_{k-1}=fM_{k-1} и x_k<=f x_k) или M_{k-1}<fM_{k-1} <=>
(f\in G_{k-1} и x_k<=f x_k) или f\not\in G_{k-1}. =>
(\forall f: f\in <S,R> => M_k<=fM_k) <=> \forall f\in G_{k-1}: x_k<=f x_k.
Т.е. в качестве x_k надо брать все, удовлетворяющие последнему св-ву. Поскольку
G_{k-1} может принимать только 10 значений (могу ошибаться):
<S,R>, <S^2,R>, <R>,
<S>, <S^2>, <>=<e>,
<RS>, <RS^2>, <RS^3>, <RS,S^2>,
все варианты для x_k можно загнать в таблицу, т.е. для 4-ок и для 8-ок будет
таблица please_give_me_the_i_th_possible_value_of_x_k[G_{k-1},i].
Легко проверить, что G_k=G_{k-1} \cap G(x_k) -- пригодится для перебора
x_{k+1}. G_k можно положить в ту же таблицу рядом с x_k.
Получается рекурсивный перебор, следующему шагу передается M_k и G_k.
M_0=(), G_0=<S,R>. В случае нечетного n последний шаг рекурсии должен еще
M_0=(), G_0=<S,R>перебрать 2 значения центрального элемента.
Чтобы быстрее работало, при G_{k-1}=<> для восьмерок можно перебирать x_k без
таблицы, прямо циклом, G_k=G_{k-1} \cap G(x_k)=<>.
AP> Оговорюсь, что
AP> 1) не важен порядок в каком будут получатся эти варианты расстановки
AP> 2) важно получать только правильные варианты; моделирование всех
AP> вариантов с последующей проверкой/отбраковкой -- не устраивает.
Лишних не перебирается, т.к. все циклы идут по непустым множествам.
nOkA. Alexey.
--- GoldED+/386 1.1.4.7
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Простенькая задача 
