Простенькая задача

From

Alexey Kruglov (2:5015/70.5)

To

Andrew Plyako

Date

2002-05-09T20:32:08Z

Area

RU.ALGORITHMS

nPuBeT, Andrew!

Вторник 07 Мая 2002 22:44, Andrew Plyako wrote to All:

 AP> Есть матрица (двумерный массив) n на n. Надо в цикле перебрать все
 AP> варианты расстановки 0 и 1 в этой матрице; все варианты __с точностью
 AP> до отражений/поворотов__.

 AP> Какой алгоритм можно предложить? Просто промоделировать все 2^{n^2}
 AP> вариантов расстановки 0 и 1 несложно. Но как при этом "пропустить" уже
 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>, уже подобрано. Надо перебрать все начала длины 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)