Изменения

Чтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1.

Для n = 1 год Грея выглядит так:

{1} --- n! различных перестановок отличных друг от друга в одной транспозиции (очевидно).

Будем строить код Грея для перестановок длины n = k. Предположим, что нам известен код Грея для перестановок длиной n = k - 1. Возьмем первую перестановку из нам известного кода. Пусть она выглядит так:

{a1, a2, a3, ..., ak-1} ,где ai при i = 1, 2, 3, ..., k --- элементы перестановки.

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

{ak, a1, a2, a3, ..., ak - 1}

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

{ak, a1, a2, a3, ..., ak - 1} (1)

{a1, ak, a2, a3, ..., ak - 1} (2)

{a1, a2, ak, a3, ..., ak - 1}

{a1, a2, a3, ak, ..., ak - 1}

..........................

{a1, a2, a3, ..., ak, ak - 1}

{a1, a2, a3, ..., ak - 1, ak} (3)

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

{a2, a1, a3, ..., ak - 1}

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

{a2, a1, a3, ..., ak - 1, ak} (4)

{a2, a1, a3, ..., ak, ak - 1}

..........................

{a2, a1, a3, ak, ..., ak - 1}

{a2, a1, ak, a3, ..., ak - 1}

{a2, ak, a1, a3, ..., ak - 1}

{ak, a2, a1, a3, ..., ak - 1}

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

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