94
правки
Изменения
Нет описания правки
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам $f$ и $g$, соединены ребром, если $g$ образуется из $f$ однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.
== Пример применения алгоритма ==
Рассмотрим код Грея для длины $n = 2$:
{2, 1}
{1, 2}
Тогда следуя алгоритму полученный код будет выглядеть так(жирным выделены элементы, которые поменялись):
{3, 2, 1} берем первую перестановку и добавляем в начало тройку
{'''2''', '''3''', 1} двигаем до последней позиции
{2, '''1''', '''3'''}
{'''1''', '''2''', 3} берем следующую перестановку и записываем тройку в конец
{1, '''3''', '''2'''} двигаем в начало
{'''3''', '''1''', 2}
Код Грея получен.
== Псевдокод получения следующего кода Грея ==
