Изменения

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

{| border="1" cellpadding="3" | $n = 2 $ || n = 3 $\{1, 2\}$ || $\{2, 1\}$

| {1, 2} $n = 3$ || $\{1, 2, 3\} |- | {2, 1} $ || $\{1, 3, 2\} |- | $ || $\{3, 1, 2\} |- | $ || $\{3, 2, 1\} |- | $ || $\{2, 3, 1\} |- | $ || $\{2, 1, 3\} $

Будем строить код Грея для длины $n = k$. Предположим, что нам известен код Грея для перестановок длиной $n = k - 1$. Возьмем первую перестановку из известного нам кода. Пусть она выглядит такОна имеет следующий вид: {a₁, a₂, a₃, ..., a_k-1} ,где $a_{i}$ при $i = 1, 2, 3, ..., k$ {{---}} элементы перестановки. Элемент $a_\{k}$ запишем в начало этой перестановки: {'''a_k'''a_1, a₁a_2, a₂a_3, a₃\dots, ..., 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₃Сначала запишем $k$ в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями (подчёркнуты пары переставляемых элементов)..., '''a_k''', a_{k - 1}}

*$\{a_{\underline{k, a_1}, a_2, a_3, \dots, a_{k-1}\}$* $\{a_1, \underline{k, a_2}, a_3, \dots, a_{k-1}\}$* $\{a_1, a_2, \underline{k, a_3}, \dots, a_{k-1}\}$* $\{a_1, a_2, a_3, \underline{k, \dots}, a_{k-1}\}$* $\{a_1, a_2, a_3, \dots, \underline{k, a_{k-1}}}\}$* $\{a_1, a₂a_2, a₃a_3, ...\dots, '''a_{a_{k - 1}'''}, '''a_k'''\} (3)$

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