Коды Грея для перестановок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построения Кода Грея для перестановок)
(Построения Кода Грея для перестановок)
Строка 48: Строка 48:
 
Чтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1.
 
Чтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1.
 
Для n = 1 год Грея выглядит так:
 
Для n = 1 год Грея выглядит так:
 +
  
 
{1} --- n! различных перестановок отличных друг от друга в одной транспозиции (очевидно).  
 
{1} --- n! различных перестановок отличных друг от друга в одной транспозиции (очевидно).  
 +
  
 
Будем строить код Грея для перестановок длины n = k. Предположим, что нам известен код Грея для перестановок длиной n = k - 1. Возьмем первую перестановку из нам известного кода. Пусть она выглядит так:
 
Будем строить код Грея для перестановок длины n = k. Предположим, что нам известен код Грея для перестановок длиной n = k - 1. Возьмем первую перестановку из нам известного кода. Пусть она выглядит так:
 +
  
 
{a1, a2, a3, ..., ak-1} ,где ai при i = 1, 2, 3, ..., k --- элементы перестановки.
 
{a1, a2, a3, ..., ak-1} ,где ai при i = 1, 2, 3, ..., k --- элементы перестановки.
 +
  
 
Элемент ak запишем в начало этой перестановки:
 
Элемент ak запишем в начало этой перестановки:
 +
  
 
{ak, a1, a2, a3, ..., ak - 1}
 
{ak, a1, a2, a3, ..., ak - 1}
 +
  
 
Будем "двигать" этот элемент ak влево, меняя его с соседним:
 
Будем "двигать" этот элемент ak влево, меняя его с соседним:
 +
  
 
{ak, a1, a2, a3, ..., ak - 1} (1)
 
{ak, a1, a2, a3, ..., ak - 1} (1)
 +
 
{a1, ak, a2, a3, ..., ak - 1} (2)
 
{a1, ak, a2, a3, ..., ak - 1} (2)
 +
 
{a1, a2, ak, a3, ..., ak - 1}
 
{a1, a2, ak, a3, ..., ak - 1}
 +
 
{a1, a2, a3, ak, ..., ak - 1}
 
{a1, a2, a3, ak, ..., ak - 1}
 +
 
..........................
 
..........................
 +
 
{a1, a2, a3, ..., ak, ak - 1}
 
{a1, a2, a3, ..., ak, ak - 1}
 +
 
{a1, a2, a3, ..., ak - 1, ak} (3)
 
{a1, a2, a3, ..., ak - 1, ak} (3)
 +
  
 
Получим k различных перестановок, отличающихся в одной транспозиции. Возьмем следующую строку из кода Грея для перестановок длиной n = k - 1, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):
 
Получим k различных перестановок, отличающихся в одной транспозиции. Возьмем следующую строку из кода Грея для перестановок длиной n = k - 1, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):
 +
  
 
{a2, a1, a3, ..., ak - 1}
 
{a2, a1, a3, ..., ak - 1}
 +
  
 
Элемент ak записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:
 
Элемент ak записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:
 +
  
 
{a2, a1, a3, ..., ak - 1, ak} (4)
 
{a2, a1, a3, ..., ak - 1, ak} (4)
 +
 
{a2, a1, a3, ..., ak, ak - 1}
 
{a2, a1, a3, ..., ak, ak - 1}
 +
 
..........................
 
..........................
 +
 
{a2, a1, a3, ak, ..., ak - 1}
 
{a2, a1, a3, ak, ..., ak - 1}
 +
 
{a2, a1, ak, a3, ..., ak - 1}
 
{a2, a1, ak, a3, ..., ak - 1}
 +
 
{a2, ak, a1, a3, ..., ak - 1}
 
{a2, ak, a1, a3, ..., ak - 1}
 +
 
{ak, a2, a1, a3, ..., ak - 1}
 
{ak, a2, a1, a3, ..., ak - 1}
 +
  
 
Опять получили k различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной n = k - 1, записываем в ее начало элемент ak и двигаем его вправо, как для первой перестановки и т.д.
 
Опять получили k различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной n = k - 1, записываем в ее начало элемент ak и двигаем его вправо, как для первой перестановки и т.д.
 +
  
 
Для каждой перестановки длиной n = k - 1 (всего их (k - 1)!) мы получили k новых перестановок. Итого k•(k - 1)! = k! перестановок. Все они различны, т.к. для любых двух перестановок из нового кода Грея ak стоит на разных позициях,а если ak стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1. Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют ak на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.
 
Для каждой перестановки длиной n = k - 1 (всего их (k - 1)!) мы получили k новых перестановок. Итого k•(k - 1)! = k! перестановок. Все они различны, т.к. для любых двух перестановок из нового кода Грея ak стоит на разных позициях,а если ak стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1. Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют ak на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.

Версия 06:52, 16 ноября 2011

код Грея для перестановки при n = 2
1 2
2 1
код Грея для перестановки при n = 3
1 2 3
2 1 3
2 3 1
3 2 1
3 1 2
1 3 2
код Грея для перестановки при n = 4
1 2 3 4 
2 1 3 4 
2 3 1 4 
2 3 4 1 
3 2 4 1 
3 2 1 4 
3 1 2 4 
1 3 2 4 
1 3 4 2 
3 1 4 2 
3 4 1 2 
3 4 2 1 
4 3 2 1 
4 3 1 2 
4 1 3 2 
1 4 3 2 
1 4 2 3 
4 1 2 3 
4 2 1 3 
4 2 3 1 
2 4 3 1 
2 4 1 3 
2 1 4 3 
1 2 4 3 

Определение

Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.

Элементарной транспозицией называют транспозиция двух соседних элементов, то есть обмен местами двух соседних элементов.

Построения Кода Грея для перестановок

Чтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1. Для n = 1 год Грея выглядит так:


{1} --- n! различных перестановок отличных друг от друга в одной транспозиции (очевидно).


Будем строить код Грея для перестановок длины n = k. Предположим, что нам известен код Грея для перестановок длиной n = k - 1. Возьмем первую перестановку из нам известного кода. Пусть она выглядит так:


{a1, a2, a3, ..., ak-1} ,где ai при i = 1, 2, 3, ..., k --- элементы перестановки.


Элемент ak запишем в начало этой перестановки:


{ak, a1, a2, a3, ..., ak - 1}


Будем "двигать" этот элемент ak влево, меняя его с соседним:


{ak, a1, a2, a3, ..., ak - 1} (1)

{a1, ak, a2, a3, ..., ak - 1} (2)

{a1, a2, ak, a3, ..., ak - 1}

{a1, a2, a3, ak, ..., ak - 1}

..........................

{a1, a2, a3, ..., ak, ak - 1}

{a1, a2, a3, ..., ak - 1, ak} (3)


Получим k различных перестановок, отличающихся в одной транспозиции. Возьмем следующую строку из кода Грея для перестановок длиной n = k - 1, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):


{a2, a1, a3, ..., ak - 1}


Элемент ak записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:


{a2, a1, a3, ..., ak - 1, ak} (4)

{a2, a1, a3, ..., ak, ak - 1}

..........................

{a2, a1, a3, ak, ..., ak - 1}

{a2, a1, ak, a3, ..., ak - 1}

{a2, ak, a1, a3, ..., ak - 1}

{ak, a2, a1, a3, ..., ak - 1}


Опять получили k различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной n = k - 1, записываем в ее начало элемент ak и двигаем его вправо, как для первой перестановки и т.д.


Для каждой перестановки длиной n = k - 1 (всего их (k - 1)!) мы получили k новых перестановок. Итого k•(k - 1)! = k! перестановок. Все они различны, т.к. для любых двух перестановок из нового кода Грея ak стоит на разных позициях,а если ak стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1. Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют ak на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.

Сведение задачи построение кода Грея для перестановок к графам

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам [math]f[/math] и [math]g[/math], соединены ребром, если [math]g[/math] образуется из [math]f[/math] однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.

См. также

Литература

Романовский, И.В. Дискретный Анализ - Санкт-Петербург 2003 стр. 39-41