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