Коды Грея для перестановок — различия между версиями
Niko (обсуждение | вклад) (→Построения Кода Грея для перестановок) |
Niko (обсуждение | вклад) (→Построения Кода Грея для перестановок) |
||
| Строка 45: | Строка 45: | ||
== '''Построения Кода Грея для перестановок''' == | == '''Построения Кода Грея для перестановок''' == | ||
Строим из рекурсивынх соображений. При фиксированной перестановки из <math>k - 1</math> элемента можно перебрать все <math>k</math> вариантов добавления к этой перестановке элемента <math>k</math>, и этот перебор можно осуществить передвигая элемент <math>k</math> каждый раз на соседнее место, Например | Строим из рекурсивынх соображений. При фиксированной перестановки из <math>k - 1</math> элемента можно перебрать все <math>k</math> вариантов добавления к этой перестановке элемента <math>k</math>, и этот перебор можно осуществить передвигая элемент <math>k</math> каждый раз на соседнее место, Например | ||
| − | 365214 | + | 365214'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 |
== '''Сведение задачи построение кода Грея для перестановок к графам''' == | == '''Сведение задачи построение кода Грея для перестановок к графам''' == | ||
Версия 21:42, 9 декабря 2010
код Грея для перестановки при 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 |
Содержание
Определение
Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.
Построения Кода Грея для перестановок
Строим из рекурсивынх соображений. При фиксированной перестановки из элемента можно перебрать все вариантов добавления к этой перестановке элемента , и этот перебор можно осуществить передвигая элемент каждый раз на соседнее место, Например
3652147 -> 3652174 -> 3652714 -> 3657214
Сведение задачи построение кода Грея для перестановок к графам
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.
