ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Elvira Svirshchova                   2:461/9.21     06 Jun 2002  05:14:00
 To : Alexey Kruglov
 Subject : Матрица из нулей и единиц
 -------------------------------------------------------------------------------- 
 

 
    Вы спрашивали, как определить G(k) в моем решении. Отвечу на Ваш вопрос
 применительно к Вашему выбору нумерации элементов матрицы по четверкам и
 восьмеркам. Предварительно несколько пояснений к понятиям и обозначениям,
 отличающимся от Ваших. В качестве исходной беру матрицу nxn, заполненную нулями,
 и ищу варианты замены L ее элементов единицами, L=1,2,..., (n^2)/2, при которых 
 матрица является канонической.(Остальные канонические варианты искомой матрицы
 получаются инвертированием элементов уже найденных матриц.)
    Пусть M(L) - вектор, представляющий матрицу nxn c L единицами, а M(l) - его
 левая часть с l единицами, lin{1,2,...,L}, расположение которых уже выбрано.
 Вектор M(l) является каноническим, если лексикографически он старше или _равен_ 
 его значению после преобразования элементами группы <S,R>. Дальше - как у Вас:
 G(l) - подгруппа группы <S,R>, элементы которой переводят элеметны M(l) в себя, 
 т.е. которым соответствует знак равенства при проверке каноничности M(l).
    Мое предложение заключается в следующем. Mножество координат вектора
 M(L)\M(l) (т.е. правую часть вектора M(L), которая остается после исключения
 координат M(l) ), каждый раз перед переходом от M(l) к M(l+1) следует разбить на
 классы эквивалентности по G(l). Тогда для получения канонических вариантов
 M(l+1) достаточно (l+1)-ю единицу располагать на старших (крайних слева)
 местах каждого класса эквивалентности.
 
    Для иллюстрации построения канонического вектора M(l) беру Ваш пример. 
 Последовательность элементов матрицы в векторе
 M(L)=(x_1,x_2,...,x_16) выбрана так:
 
                       x_5   x_9  x_16  x_8
                       x_10  x_1  x_4  x_15
                       x_11  x_2  x_3  x_14
                       x_6  x_12  x_13  x_7
 
    Исходной матрице с нулевыми элементами соответствует вектор M(L) из нулей,
 M(l)=M(0) и группа G(l)=G(0), которая совпадает с группой <S,R>. Классы
 эквивалентности вектора M(L)\M(0) - это ваши четверки и восьмерки: элементы с
 номерами 1,2,3,4 составляют старший класс эквивалентнтости, с номерами 5,6,7,8 -
 следующий по старшинству, с номерами 9,10,...,16 - последний класс.
 Следовательно, канонические векторы M(1) - это
 
               (1),
               (0,0,0,0,1),
               (0,0,0,0,0,0,0,0,1).
 
    Пусть выбран первый из них в качестве M(1). Группа G(1) cодержит, кроме
 единичного элемента, отображение матрицы относительно главной диагонали. Для
 определения канонических вариантов M(2) разбиваем на классы эквивалентности по
 G(1) вектор M(L)\M(1). Перечисляю эти классы, обозначая относящиеся к ним
 элементы M(L) их порядковыми номерами: (2,4), (3),(5), (6,8), (7), (9,10),
 (11,16), (12,15), (13,14). Канонические векторы M(2):
 
               (1,1)
               (1,0,1)
               (1,0,0,0,1)
               (1,0,0,0,0,1)
               (1,0,0,0,0,0,1)
               (1,0,0,0,0,0,0,0,1)
               (1,0,0,0,0,0,0,0,0,0,1)
               (1,0,0,0,0,0,0,0,0,0,0,1)
               (1,0,0,0,0,0,0,0,0,0,0,0,1).
 
    Выберем в качестве M(2) первый из них. Группа G(2) состоит из единичного
 элемента и отражения матрицы относительно горизонтальной оси. Классы
 эквивалентности M(L)\M(2) по этим симметриям: (3,4), (5,6), (7,8), (9,12),
 (10,11), (13,16), (14,15). Канонические векторы M(3):
 
               (1,1,1)
               (1,1,0,0,1)
               (1,1,0,0,0,0,1)
               (1,1,0,0,0,0,0,0,1)
               (1,1,0,0,0,0,0,0,0,1)
               (1,1,0,0,0,0,0,0,0,0,0,0,1)
               (1,1,0,0,0,0,0,0,0,0,0,0,0,1).
 
 (...)
 
     Пусть M(4)=(1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0). Соответствующая группа G(4)
 совпадает с G(0). Классы эквивалентности вектора M(L)\M(4): (5,6,7,8),
 (9,19,...,16). Канинические векторы M(5):
 
                (1,1,1,1,1),
                (1,1,1,1,0,0,0,0,1).
 
 и т.д.
 
                      С уважением!
                                  Elvira Svirshchova
 ---
  * Origin:  Hадеемся на лучшее... (FidoNet 2:461/9.21)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор