ЗАДАЧА ОБ ОЖЕРЕЛЬЯХ. АЛГОРИТМЫ НАХОЖДЕНИЯ РЕШЕНИЙ. ПРОГРАММНАЯ РЕАЛИЗИЦИЯ ЗАДАЧИ

Введение

В данной статье рассматриваются некоторые алгоритмы решения задачи об ожерельях. В данной работе уделим особое внимание Лемме Бёрнсайда, теореме Пойа и некоторым соответствующим определениям, так как этот теоретический материал поможет реализовать программный продукт решения задачи, что является нашей целью.

Актуальность

В чем же состоит актуальность выбранной нами темы? Ответ на данный вопрос прост. В теории кодирования некоторые вопросы связаны с известной комбинаторной задачей, которая называется «Задача об ожерельях».

Какое же отношение имеет задача об ожерельях к проблемам кодирования? А дело вот в чем: при передаче закодированных сообщений на передающей и приемной сторонах канала связи должна выполняться синхронизация. Синхронность работы обеспечивается тактовыми генераторами. При сбоях этих генераторов происходит нарушение синхронизации, а это в свою очередь приведет к неправильному восприятию символов. Т.е. в качестве начального символа кодового слова воспринимается такой символ, который и не является начальным. Отсюда вытекает и актуальность задачи построения кодов, которые способны восстанавливать синхронизацию.

Основные определения

Действие группы  на множестве  – это гомоморфизм групп , где – группа биекций. Обозначается .

При фиксированном действии  для каждого элемента  определены его орбита  и стабилизатор – подгруппа .

  Орбиты действия – классы эквивалентности по отношению
.

 Действие  называется

·     Транзитивным, если все множество  – единственная орбита, т.е. ;

·     Эффективным, если его ядро неэффективности  тривиально.

Функция Эйлера  определяется для всех целых положительных a и представляет собою число чисел ряда  взаимно простых с a.

Инвариантной перестановкой будет являться любая перестановка, полученная из данной циклическим сдвигом.

Перестановка – это упорядоченный набор чисел , обычно трактуемый как биекция на множеств , которая числу  ставит в соответствие i-ый элемент из набора. Число  при этом называется порядком перестановки.

Циклом длины называется такая перестановка которая тождественна на всём множестве X кроме подмножества  и , . Обозначается 

Формулировка задачи об ожерельях

Требуется посчитать количество ожерелий из  бусинок, каждая из которых может быть покрашена в один из  цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать, т.е. разрешается сделать циклический сдвиг. Решение данной задачи опирается на лемму Бёрнсайда и теорему Пойа.

Лемма Бёрнсайда

Пусть группа  действует на множество . Будем называть два элемента  и  эквивалентными. Если  для некоторого , то два элемента  и  являются эквивалентными. Тогда число классов эквивалентности равно сумме числа стабилизаторов по всем элементам группы , делённой на размер этой группы: , — количество стабилизаторов для элемента .

Обобщением леммы Бёрнсайда является Теорема Пойа. Она позволяет находить количество классов эквивалентности, используя величину - количество циклов в перестановке.

Теорема Пойа

 где — количество различных классов эквивалентности, - количество циклов в перестановке , - количество различных состояний одного элемента.

Первый алгоритм нахождения решения задачи про ожерелья

Дано: бусины  различных цветов, ожерелье состоит из  бусин.

Для решения данной задачи мы обратимся к теореме Пойа, воспользовавшись нижеприведенной формулой: 

Из условия видно, что любая перестановка, которая получается путем циклического сдвига, будет инвариантной данной. Очевидно, что всего инвариантных перестановок в каждом классе  (т.к. для каждой перестановки длины  существует  инвариантная перестановка). Следующим шагом будет нахождение . Обратим внимание, что в i-ой перестановке на позиции  стоит элемент . А также видим, что элемент  переходит в элемент , где . Следовательно, длина цикла для -ой перестановки равна , где -НОД,НОК.
Откуда следует что:  где — количество различных ожерелий, получаемые из  бусин  различных цветов.

Если бусины раскрашиваем в один цвет, то они принадлежат одной орбите, т.е. одна получается из другой путем преобразования симметрии. У тождественного поворота есть  неподвижных точек. Обратившись к лемме Бёрнсайда, получаем, что число орбит равняется , где - минимальное число, причем  делится на , число их раскрасок . Сумма инвариантных раскрасок для всех поворотов: 

В последней сумме  слагаемых (— функция Эйлера), для которых . Если же , то .

Количество , меньших , определяется перебором чисел вида  , и обязательно проверяются эти числа условием  .

По определению функции  таких чисел будет . Сделав подстановку, получаем:  Тогда количество различных
ожерелий будем высчитывать по формуле: 

Второй алгоритм нахождения решения про ожерелья

Пусть теперь ожерелья считаются одинаковыми, они переходят друг в друга не только поворотом, но и отражением относительно некоторой оси, которая может располагаться на двух противоположных бусин, или ось лежит на противоположных пустотах, а также ось может проходить через бусину, если их нечетное количество. Для решения задачи по второму алгоритму будем пользоваться леммой Бёрнсайда.

Сначала отметим, что в качестве операций требуется рассматривать только повороты и отражения. Возможные операции:

1)  Поворот и отражение – отражение.

2)  Отражение и поворот – отражение.

3)  Отражение и отражение – поворот.

Пронумеруем наши бусинки по часовой стрелке. Поворот не меняет порядка. Нетрудно понять, что и отражение не меняет порядка, а меняет лишь направление обхода бусин. Если мы сначала совершим поворот, а потом проведем отражение относительно какой-нибудь оси, то мы можем получить, то же самое и обычным отражением относительно какой-то оси. Такая ось будет, ведь всегда можно выбрать ось, которая поставит первую бусину на своё первоначальное место, поменяв направление обхода. Поэтому поворот и отражение не добавляет нам новой операции.  Аналогично рассуждая во втором пункте, получим такой же вывод. В третьем пункте мы дважды меняем направление обхода, но не изменяем порядка. Поэтому эту операцию заменит обычный поворот.

Выделим два случая, когда число бусин нечетное и четное.

Случай 1. Дано: число бусин - нечётное. Тогда мы имеем  осей, которые проходят через каждую бусину. Рассмотрим одну ось. Возьмём саму бусину, через которую проходит выбранная ось, и половину бусин с одной стороны от этой оси. Окрасим выбранные бусины в различные цвета, а остальная половина бусин по ним однозначно восстановится. Таким образом, количество неподвижных точек для одной оси получим . Операций в группе станет в два раза больше:  (т.е. сдвигов и  отражений).

Воспользуемся леммой Бёрнсайда, взяв формулу: 

. Первые  операций — повороты, сумма их количества неподвижных точек принимает значение , где - количество ожерелий из  бусинок  различных цветов без отражений (вышеприведенный алгоритм). Деление в предыдущем алгоритме происходило на , а здесь на . Следующие  операций — отражения. Сумма неподвижных точек будет .

Случай 2. Дано: число бусин - чётное. В данном случае мы имеем  осей, проходящих через пустоты между бусинами. Можно выбрать по  бусин и дать им различные цвета. Остальная половина восстановится по ним. Для данных осей количество неподвижных точек будет . Ещё у нас есть  осей, проходящих через бусины. В данных случаях мы можем выбрать по бусин. То есть количество неподвижных точек будет . Операций в группе также . Снова воспользовавшись Леммой Бёрнсайда, получим:

Теперь вернемся к проблемам кодирования. Разложим  бусин по окружности, указав для каждой бусины номер ее цвета. Если совершить обход этой окружности в определенном направлении, начав с какой-то бусины, то ожерелью из  бусинок будет соответствовать слово (), где  - это номер цвета i-й бусины. Т.к. обход можно начать с любой бусины, поэтому любому ожерелью соответствует  слов, получаемых одно из другого путем циклических сдвигов. Чтобы вывести формулу для нахождения числа основных слов, воспользуемся функцией Мёбиуса

                        , если ;

                       0 - в остальных случаях.

Обозначив общее число основных слов длины  алфавита из  символов ,получим . Полученная формула позволяет найти число интересующих нас ожерелий, которое, очевидно, равно 

Один из возможных путей решения - рассмотрение множества n-буквенных кодовых слов, удовлетворяющего такому ограничению: если () и ()- кодовые слова, то никакое из «перекрытий» между ними

(), (),…, () не является кодовым словом. Коды, обладающие этим свойством, называются синхронизируемыми. Решение задачи об ожерельях позволит узнать, насколько велика плата за усовершенствование кода. Действительно, если  - кодовое слово синхронизируемого кода, то кодовым словом не может быть его циклический сдвиг, так как он является перекрытием для пары .

Следовательно, обозначенное  максимальное число n-буквенных слов синхронизируемого кода, который использует алфавит из  символов, не превосходит числа несоставных ожерелий с  бусинами  различных цветов.

.

В итоге, получаем верхнюю границу для числа n -буквенных кодовых слов синхронизируемого кода: 

Реализация программного продукта

Формулировка конкретной задачи: ожерелье состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, если номера этих колечек отличаются более чем на единицу. Необходимо упорядочить колечки в порядке возрастания номеров вдоль нити по часовой стрелке.

Реализация решения данной задачи разработана на языке программирования С++. Среда разработки - Microsoft Visual Studio.

class Functions{

public:

  static int ReadInt(){

           int value = 0;

           scanf("%d", &value);

           return value;}

  static int Abs(int x)

           {return (x < 0) ? -x: x;}

};

class Data{

private: …

public: …

  bool Swap(int i, int j){

           Data &data = *this;

           if (Functions::Abs(data[i]-data[j]) < 2)

                     return false;

           int t = data[i];

           data[i] = data[j];

           data[j] = t;

           return true;}

…

class Solver{

public:

  static void Solve(Data &data){

           while (true){

                     bool end = true;

                     for (int i = 0; i < data.Size(); i++){

                              if (data[i] > data[i+1])

                                       continue;

                              if (data.Swap(i, i+1)){

                                       printf("%d %d\n", data[i+1], data[i]);

                                       end = false;}

                     } if (end)

                      break;

           }printf("0\n");

  };}; …

Заключение

Таким образом, в данной работе мы достигли своей цели, представив программную реализацию решения конкретной задачи об ожерельях, а также рассмотрели различные алгоритмы нахождения решения.