Простенькая задача
- From
- Elvira Svirshchova (2:461/9.21)
- To
- Andrew Plyako
- Date
- 2002-05-11T21:27Z
- Area
- RU.ALGORITHMS
Приветствую, Andrew!
Tuesday May 07 2002,23:44, Andrew Plyako writes to All:
AP> Есть матрица (двумерный массив) n на n. Надо в цикле перебрать все
AP> варианты расстановки 0 и 1 в этой матрице; все варианты __с точностью
AP> до отражений/поворотов__.
AP>
AP> Какой алгоритм можно предложить? Просто промоделировать все 2^{n^2}
AP> вариантов расстановки 0 и 1 несложно. Но как при этом "пропустить" уже
AP> полученные (с точностью до поворота) варианты?
Алгоритм, предложенный А. Кругловым, основан на идее канонического упорядочения векторов М, которое позволяет из множества вариантов М, эквивалентных по f in <a,b>, выбрать старший (или младший) вариант в качестве единственного представителя этого множества. Здесь сохранены принятые им обозначения. Предлагаю способ построения канонического вектора М, который не требует проверок его старшинства преобразованиями f in <a,b>.
Элементы группы <а,б> буду называть симметриями, так как они отражают симметрии еще незаполненной (пустой) матрицы n на n, совпадающей с группой симметрий квадрата.
Разобьем множество недиагональных элементов пустой матрицы на
8 подмножеств, образующих треугольники, ограниченные ее осями симметрий. Все треугольники эквивалентны между собой по симметриям матрицы. Т.е. для любой пары треугольников найдется такое преобразование f in <a,b>, которое их меняет местами. Выберем индексы i координат x_i вектора М таким образом, чтобы одинаковые по старшинству в алфавите (1,2,...,м) элементы каждой пары треугольников переходили друг в друга, когда один треугольник приводится к другому симметриями матрицы. Привожу пример такого выбора индексов i
для матрицы 6х6.
- 11 9 10 12 -
24 - 1 2 - 14
23 8 - - 3 13
21 7 - - 4 15
22 - 6 5 - 16
- 20 19 17 18 -
Лексикографическим порядком на индексах i индуцируется порядок на треугольниках. Вектор М составим из подмножеств элементов матрицы, соответствующих треугольникам, с учетом старшинства как треугольников, так и их элементов:
M=(х_1, х_9, х_11,|х_2, х_10, х_12,|х_3, х_13, х_14,|...|х_8, х_23, х_24).
Вертикальными чертами разделены взаимозаменяемые части вектора М (с учетом симметрий матрицы). Теперь задача сводится к такому выбору координат x_i вектора М, при котором его взаимозаменяемые части упорядочены лексикографически, например, в алфавите (1,0). В этом случае никакими преобразованиями f in <a,b> вектор М невозможно сделать старше. Следовательно, он является каноническим.
Дальше приведены примеры конструктивного перечисления канонических векторов М для матрицы 6х6 в порядке их лг убывания.
Векторы М с одной единицей:
(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0).
Векторы М с четырьмя единицами:
(1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
(0,1,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0),
(0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0), (0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0),
(0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0).
С уважением!
Эльвира Свирщёва
---
* Origin: Надеемся на лучшее... (FidoNet 2:461/9.21)