Коды Грея для перестановок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построения Кода Грея для перестановок)
Строка 44: Строка 44:
  
 
== '''Построения Кода Грея для перестановок''' ==
 
== '''Построения Кода Грея для перестановок''' ==
   
+
Строим из рекурсивынх соображений. При фиксированной перестановки из <math>k - 1</math> элемента можно перебрать все <math>k</math> вариантов добавления к этой перестановке элемента <math>k</math>, и этот перебор можно осуществить передвигая элемент <math>k</math> каждый раз на соседнее место, Например
 
+
  365214''''7'''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214
  
 
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
 
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==

Версия 21:41, 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 

Определение

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

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

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

365214'7' -> 3652174 -> 3652714 -> 3657214

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

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

См. также