Коды Грея для перестановок

код Грея для перестановки при n = 2 1 2 2 1

код Грея для перестановки при n = 3 1 2 3 2 1 3 2 3 1 3 2 1 3 1 2 1 3 2

код Грея для перестановки при n = 4 1 2 3 4 2 1 3 4 2 3 1 4 2 3 4 1 3 2 4 1 3 2 1 4 3 1 2 4 1 3 2 4 1 3 4 2 3 1 4 2 3 4 1 2 3 4 2 1 4 3 2 1 4 3 1 2 4 1 3 2 1 4 3 2 1 4 2 3 4 1 2 3 4 2 1 3 4 2 3 1 2 4 3 1 2 4 1 3 2 1 4 3 1 2 4 3

Определение

Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.

Построения Кода Грея для перестановок

Строим из рекурсивынх соображений. При фиксированной перестановки из [math]k - 1[/math] элемента можно перебрать все [math]k[/math] вариантов добавления к этой перестановке элемента [math]k[/math], и этот перебор можно осуществить передвигая элемент [math]k[/math] каждый раз на соседнее место, Например

3652147 -> 3652174 -> 3652714 -> 3657214

Сведение задачи построение кода Грея для перестановок к графам

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.

См. также

• Коды Грея
• Комбинаторные объекты
• Гамильтонов путь