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

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

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

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

<wikitex>

Определение

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

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

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

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

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

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

{a₁, a₂, a₃, ..., a_k-1} ,где a_i при i = 1, 2, 3, ..., k - элементы перестановки.

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

{a_k, a₁, a₂, a₃, ..., a_{k - 1}}

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

{a_k, a₁, a₂, a₃, ..., a_{k - 1}} (1)

{a₁, a_k, a₂, a₃, ..., a_{k - 1}} (2)

{a₁, a₂, a_k, a₃, ..., a_{k - 1}}

{a₁, a₂, a₃, a_k, ..., a_{k - 1}}

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

{a₁, a₂, a₃, ..., a_k, a_{k - 1}}

{a₁, a₂, a₃, ..., a_{k - 1}, a_k} (3)

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

{a₂, a₁, a₃, ..., a_{k - 1}}

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

{a₂, a₁, a₃, ..., a_{k - 1}, a_k} (4)

{a₂, a₁, a₃, ..., a_k, a_{k - 1}}

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

{a₂, a₁, a₃, a_k, ..., a_{k - 1}}

{a₂, a₁, a_k, a₃, ..., a_{k - 1}}

{a₂, a_k, a₁, a₃, ..., a_{k - 1}}

{a_k, a₂, a₁, a₃, ..., a_{k - 1}}

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

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

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

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

См. также

• Коды Грея
• Комбинаторные объекты
• Гамильтонов путь

Литература

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