Коды Грея для перестановок
код Грея для перестановки при 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 |
Определение
Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.
Построения Кода Грея для перестановок
Строим из рекурсивынх соображений. При фиксированной перестановки из элемента можно перебрать все вариантов добавления к этой перестановке элемента , и этот перебор можно осуществить передвигая элемент каждый раз на соседнее место, Например
365214'7' -> 3652174 -> 3652714 -> 3657214
Сведение задачи построение кода Грея для перестановок к графам
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.
