Изменения

Элемент ak a_k запишем в начало этой перестановки:

Будем "двигать" этот элемент ak a_k влево, меняя его с соседним:

{a1a₁, aka_k, a2a₂, a3a₃, ..., ak a_{k - 1}} (2)

{a1a₁, a2a₂, aka_k, a3a₃, ..., ak a_{k - 1}}

{a1a₁, a2a₂, a3a₃, aka_k, ..., ak a_{k - 1}}

{a1a₁, a2a₂, a3a₃, ..., aka_k, ak a_{k - 1}}

{a1a₁, a2a₂, a3a₃, ..., ak a_{k - 1}, aka_k} (3)

{a2a₂, a1a₁, a3a₃, ..., ak a_{k - 1}}

Элемент ak a_k записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:

{a2a₂, a1a₁, a3a₃, ..., ak a_{k - 1}, aka_k} (4)

{a2a₂, a1a₁, a3a₃, ..., aka_k, ak a_{k - 1}}

{a2a₂, a1a₁, a3a₃, aka_k, ..., ak a_{k - 1}}

{a2a₂, a1a₁, aka_k, a3a₃, ..., ak a_{k - 1}}

{a2a₂, aka_k, a1a₁, a3a₃, ..., ak a_{k - 1}}

{aka_k, a2a₂, a1a₁, a3a₃, ..., ak a_{k - 1}}

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

Для каждой перестановки длиной n = k - 1 (всего их (k - 1)!) мы получили k новых перестановок. Итого k•(k - 1)! = k! перестановок. Все они различны, т.к. для любых двух перестановок из нового кода Грея ak a_k стоит на разных позициях,а если ak a_k стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1. Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют ak a_k на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.