Изменения

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

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

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

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

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