Изменения

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

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

<tex>\{a_2b_1, a_1b_2, a_3b_3, \dots, a_b_{k-1}\}</tex>

* <tex>\{a_2b_1, a_1b_2, a_3b_3, \dots, \underline{a_b_{k-1}, k}\}</tex>* <tex>\{a_2b_1, a_1b_2, a_3b_3, \underline{\dots, k}, a_b_{k-1}\}</tex>* <tex>\{a_2b_1, a_1b_2, \underline{a_3b_3, k}, \dots, a_b_{k-1}\}</tex>* <tex>\{a_2b_1, \underline{a_1b_2, k}, a_3b_3, \dots, a_b_{k-1}\}</tex>* <tex>\{\underline{a_2b_2, k}, a_1b_1, a_3b_3, \dots, a_b_{k-1}\}</tex>* <tex>\{k, a_2b_1, a_1b_2, a_3b_3, \dots, a_b_{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> получен.