Простенькая задача
- From
- Alexey Kruglov (2:5015/70.5)
- To
- Elvira Svirshchova
- Date
- 2002-05-14T17:59:59Z
- Area
- RU.ALGORITHMS
nPuBeT, Elvira!
Суббота 11 Мая 2002 20:27, Elvira Svirshchova wrote to Andrew Plyako:
AP>> Есть матрица (двумерный массив) n на n. Надо в цикле перебрать
AP>> все варианты расстановки 0 и 1 в этой матрице; все варианты __с
AP>> точностью до отражений/поворотов__.
ES> Алгоритм, предложенный А. Кругловым, основан на идее канонического
ES> упорядочения векторов М, которое позволяет из множества вариантов М,
ES> эквивалентных по f in <a,b>, выбрать старший (или младший) вариант в
ES> качестве единственного представителя этого множества. Здесь сохранены
ES> принятые им обозначения. Предлагаю способ построения канонического
ES> вектора М, который не требует проверок его старшинства
ES> преобразованиями f in <a,b>.
У меня, кстати, эта проверка делается один раз заранее, и результат складыватся
в таблицу.
[...]
ES> Разобьем множество недиагональных элементов пустой матрицы на
ES> 8 подмножеств, образующих треугольники, ограниченные ее осями
ES> симметрий. Все треугольники эквивалентны между собой по симметриям
ES> матрицы. Т.е. для любой пары треугольников найдется такое
ES> преобразование f in <a,b>, которое их меняет местами.
[...]
ES> - 11 9 10 12 -
ES> 24 - 1 2 - 14
ES> 23 8 - - 3 13
ES> 21 7 - - 4 15
ES> 22 - 6 5 - 16
ES> - 20 19 17 18 -
[...]
ES> M=(х_1, х_9, х_11,|х_2, х_10, х_12,|х_3, х_13, х_14,|...|х_8, х_23,
ES> х_24).
ES> Вертикальными чертами разделены взаимозаменяемые части вектора М (с
ES> учетом симметрий матрицы). Теперь задача сводится к такому выбору
ES> координат x_i вектора М, при котором его взаимозаменяемые части
ES> упорядочены лексикографически, например, в алфавите (1,0).
Назовем эквивалентными матрицы, которые переводятся друг в друга элементами
<a,b> (у меня эта группа обозначалась <S,R>). Тогда не каждый класс
эквивалентности будет содержать матрицу, в которой части так упорядочены,
поскольку, хоть <a,b> и может переставить любую пару частей, но при этом он
переставит и еще какие-то другие части (т.к. <a,b>!=S_8, которая порождается
транспозициями).
[...]
ES> Векторы М с одной единицей:
Верно.
ES> Векторы М с четырьмя единицами:
Тут не все. Например, нет такого:
(0,1,1, 0,0,1, 0,1,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0)
Результат действия на него элементов <S,R> (буду, все-таки, пользоваться такими
обозначениями):
e: (011 001 010 000 000 000 000 000)
S: (010 000 000 000 000 000 011 001)
S^2: (000 000 000 000 011 001 010 000)
S^3: (000 000 011 001 010 000 000 000)
R: (001 011 000 000 000 000 000 010)
RS: (000 010 001 011 000 000 000 000)
RS^2: (000 000 000 010 001 011 000 000)
RS^3: (000 000 000 000 000 010 001 011)
Т.е. он канонический.
Кроме того тут было всего 19 матриц, а на самом деле их >= C_{24}^4/8 > 1328,
т.к всего матриц без диагоналей с 4 единицами C_{24}^4, а в каждом классе
эквивалентности <= |<S,R>|=8 элементов.
nOkA. Alexey.
--- GoldED+/386 1.1.4.7
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)