Изменения

| $<tex>n = 2$ </tex> || $<tex>\{1, 2\}$ </tex> || $<tex>\{2, 1\}$</tex>

| $<tex>n = 3$ </tex> || $<tex>\{1, 2, 3\}$ </tex> || $<tex>\{1, 3, 2\}$ </tex> || $<tex>\{3, 1, 2\}$ </tex> || $<tex>\{3, 2, 1\}$ </tex> || $<tex>\{2, 3, 1\}$ </tex> || $<tex>\{2, 1, 3\}$</tex>

Будем строить код Грея для длины $<tex>n = k$</tex>. Предположим, что нам известен код Грея для перестановок длиной $<tex>k - 1$</tex>. Возьмем первую перестановку из известного нам кода. Она имеет следующий вид: $<tex>\{a_1, a_2, a_3, \dots, a_{k-1}\}$</tex>

Сначала запишем $<tex>k$ </tex> в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями (подчёркнуты пары переставляемых элементов).

* $<tex>\{\underline{k, a_1}, a_2, a_3, \dots, a_{k-1}\}$</tex>* $<tex>\{a_1, \underline{k, a_2}, a_3, \dots, a_{k-1}\}$</tex>* $<tex>\{a_1, a_2, \underline{k, a_3}, \dots, a_{k-1}\}$</tex>* $<tex>\{a_1, a_2, a_3, \underline{k, \dots}, a_{k-1}\}$</tex>* $<tex>\{a_1, a_2, a_3, \dots, \underline{k, a_{k-1}}\}$</tex>* $<tex>\{a_1, a_2, a_3, \dots, a_{k-1}, k\}$</tex>

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

$<tex>\{a_2, a_1, a_3, \dots, a_{k-1}\}$</tex>

Элемент $<tex>k$ </tex> записываем в конец и начинаем "двигать" его влево:

* $<tex>\{a_2, a_1, a_3, \dots, \underline{a_{k-1}, k}\}$</tex>* $<tex>\{a_2, a_1, a_3, \underline{\dots, k}, a_{k-1}\}$</tex>* $<tex>\{a_2, a_1, \underline{a_3, k}, \dots, a_{k-1}\}$</tex>* $<tex>\{a_2, \underline{a_1, k}, a_3, \dots, a_{k-1}\}$</tex>* $<tex>\{\underline{a_2, k}, a_1, a_3, \dots, a_{k-1}\}$</tex>* $<tex>\{k, a_2, a_1, a_3, \dots, a_{k-1}\}$</tex>

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

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

Рассмотрим код Грея для длины $<tex>n = 2$</tex>:

* $<tex>\{2, 1\}$</tex>* $<tex>\{1, 2\}$</tex>

* $<tex>\{\underline{3, 2}, 1\}$ </tex> {{---}} берем первую перестановку и добавляем в начало тройку* $<tex>\{2, \underline{3, 1}\}$ </tex> {{---}} двигаем до последней позиции* $<tex>\{\underline{2, 1}, 3\}$</tex>* $<tex>\{1, \underline{2, 3}\}$ </tex> {{---}} берем следующую перестановку и записываем тройку в конец* $<tex>\{\underline{1, 3}, 2\}$ </tex> {{---}} двигаем в начало* $<tex>\{3, 1, 2\}$</tex>

Получаем код Грея рекурсивно, в базовом случае ($<tex>n = 1$</tex>) возвращаем список из одной перестановки $<tex>\{n\}$</tex>.

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

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