152
правки
Изменения
→Построения Кода Грея для перестановок
== '''Построения Кода Грея для перестановок''' ==
Строим из рекурсивных соображений. При фиксированной перестановки из <math>k - 1</math> элемента можно перебрать все <math>k</math> вариантов добавления к этой перестановке элемента <math>k</math>, и этот перебор можно осуществить передвигая элемент <math>k</math> каждый раз на соседнее место, Например
365214'''7''' -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. д.
На фоне перебора позиций <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> то место
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
