Коды Грея для перестановок — различия между версиями
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'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. д. | 365214'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. д. | ||
| − | На фоне перебора позиций <math>k</math>-го элемента должны проводиться переборы перестановок меньшего порядка, к которым применяется тот же принцип, т.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6. | + | |
| + | На фоне перебора позиций <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>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> то место | ||
== '''Сведение задачи построение кода Грея для перестановок к графам''' == | == '''Сведение задачи построение кода Грея для перестановок к графам''' == | ||
Версия 22:15, 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 и т. д.
На фоне перебора позиций -го элемента должны проводиться переборы перестановок меньшего порядка, к которым применяется тот же принцип, т.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6.
Действовать будем так. Каждые итерации будем давать команду на сдвиг -го элемента, а затем менять направление движения его на противоположное и будем давать команду на сдвиг элемента с меньшим номером; для этих выделенных итераций нужно делать то же самое: на из них двигать -й элемент, а на -й итерации сменить ему направление движения, и т.д.
Построение. Кроме рабочей перестановки и её номера в факториальной системе (младший разряд - последний) потребуется иметь массив , задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу то место
Сведение задачи построение кода Грея для перестановок к графам
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.
