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

код Грея для перестановки при 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