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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Построения Кода Грея для перестановок)
(→‎Построения Кода Грея для перестановок)
Строка 44: Строка 44:
  
 
== '''Построения Кода Грея для перестановок''' ==
 
== '''Построения Кода Грея для перестановок''' ==
−
Строим из рекурсивных соображений. При фиксированной перестановки из <math>k - 1</math> элемента можно перебрать все <math>k</math> вариантов добавления к этой перестановке элемента <math>k</math>, и этот перебор можно осуществить передвигая элемент <math>k</math> каждый раз на соседнее место, Например
+
Строим из рекурсивных соображений. При фиксированной перестановки из <tex>k - 1</tex> элемента можно перебрать все <tex>k</tex> вариантов добавления к этой перестановке элемента <tex>k</tex>, и этот перебор можно осуществить передвигая элемент <tex>k</tex> каждый раз на соседнее место, Например
  
 
  365214'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. д.
 
  365214'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. д.
  
−
На фоне перебора позиций <math>k</math>-го элемента должны проводиться  
+
На фоне перебора позиций <tex>k</tex>-го элемента должны проводиться  
 
переборы перестановок меньшего порядка, к которым применяется тот же принцип, т.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6.
 
переборы перестановок меньшего порядка, к которым применяется тот же принцип, т.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6.
  
−
Действовать будем так. Каждые <math>k - 1</math> итерации будем давать команду на сдвиг <math>k</math>-го элемента, а затем менять направление движения его на противоположное и будем давать команду на сдвиг элемента с меньшим номером; для этих выделенных итераций нужно делать то же самое: на <math>k - 2</math> из них двигать <math>(k - 1)</math>-й элемент, а на <math>(k - 1)</math>-й итерации сменить ему направление движения, и т.д.
+
Действовать будем так. Каждые <tex>k - 1</tex> итерации будем давать команду на сдвиг <tex>k</tex>-го элемента, а затем менять направление движения его на противоположное и будем давать команду на сдвиг элемента с меньшим номером; для этих выделенных итераций нужно делать то же самое: на <tex>k - 2</tex> из них двигать <tex>(k - 1)</tex>-й элемент, а на <tex>(k - 1)</tex>-й итерации сменить ему направление движения, и т.д.
  
−
Построение. Кроме рабочей перестановки <math>r</math> и её номера в факториальной системе <math>t</math> (младший разряд - последний) потребуется иметь массив <math>d</math>, задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу <math>i</math> то место
+
Построение. Кроме рабочей перестановки <tex>r</tex> и её номера в факториальной системе <tex>t</tex> (младший разряд - последний) потребуется иметь массив <tex>d</tex>, задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу <tex>i</tex> то место <tex>p_i</tex>? на котором стоит <tex>i</tex> стоит в перестановке <tex>r</tex>.
  
 
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
 
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==

Версия 22:21, 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] каждый раз на соседнее место, Например 

3652147 -> 3652174 -> 3652714 -> 3657214 и т. д.

На фоне перебора позиций [math]k[/math]-го элемента должны проводиться переборы перестановок меньшего порядка, к которым применяется тот же принцип, т.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6.

Действовать будем так. Каждые [math]k - 1[/math] итерации будем давать команду на сдвиг [math]k[/math]-го элемента, а затем менять направление движения его на противоположное и будем давать команду на сдвиг элемента с меньшим номером; для этих выделенных итераций нужно делать то же самое: на [math]k - 2[/math] из них двигать [math](k - 1)[/math]-й элемент, а на [math](k - 1)[/math]-й итерации сменить ему направление движения, и т.д.

Построение. Кроме рабочей перестановки [math]r[/math] и её номера в факториальной системе [math]t[/math] (младший разряд - последний) потребуется иметь массив [math]d[/math], задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу [math]i[/math] то место [math]p_i[/math]? на котором стоит [math]i[/math] стоит в перестановке [math]r[/math].

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

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

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Коды_Грея_для_перестановок&oldid=5723»