Для $n = 1$ код Грея выглядит так:
$\{ 1 \}$
Будем строить код Грея для перестановок длины $n = k$. Предположим, что нам известен код Грея для перестановок длиной $n = k - 1$. Возьмем первую перестановку из известного нам кода. Пусть она выглядит так:
$\{a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k-1</sub>}\}$ ,где $a_{i}$ при $i = 1, 2, 3, ..., k$ {{---}} элементы перестановки.
Элемент $a_{k}$ запишем в начало этой перестановки:
$\{a_{a<sub>k}</sub>, a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
Будем "двигать" этот элемент $a_{k}$ вправо, меняя его с соседним:
$\{a_{a<sub>k}</sub>, a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$ (1)
$\{a_{a<sub>1}</sub>, a_{a<sub>k}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$ (2)
$\{a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>k}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
$\{a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, a_{a<sub>k}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
$..........................$
$\{a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k}</sub>, a_{a<sub>k - 1</sub>}\}$
$\{a_{a<sub>1}</sub>, a_{a<sub>2}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1}</sub>, a_{a<sub>k</sub>}\}$ (3)
Получим $k$ различных перестановок, отличающихся в одной транспозиции. Возьмем следующую строку из кода Грея для перестановок длиной $n = k - 1$, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):
$\{a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
Элемент $a_{k}$ записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:
$\{a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1}</sub>, a_{a<sub>k</sub>}\}$ (4)
$\{a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k}</sub>, a_{a<sub>k - 1</sub>}\}$
$..........................$
$\{a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, a_{a<sub>k}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
$\{a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>k}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
$\{a_{a<sub>2}</sub>, a_{a<sub>k}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
$\{a_{a<sub>k}</sub>, a_{a<sub>2}</sub>, a_{a<sub>1}</sub>, a_{a<sub>3}</sub>, ..., a_{a<sub>k - 1</sub>}\}$
Опять получили $k$ различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной $n = k - 1$, записываем в ее начало элемент $a_{k}$ и двигаем его вправо, как для первой перестановки и т.д.
