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

код Грея для перестановки при 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. Возьмем первую перестановку из нам известного кода. Пусть она выглядит так:

{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. Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют a_k на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.

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

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

См. также

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

Литература

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