152
правки
Изменения
→Построения Кода Грея для перестановок
Построение. Кроме рабочей перестановки <tex>r</tex> и её номера в факториальной системе <tex>t</tex> (младший разряд - последний) потребуется иметь массив <tex>d</tex>, задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу <tex>i</tex> то место <tex>p_i</tex>, на котором стоит <tex>i</tex> стоит в перестановке <tex>r</tex>.
''Начальное состояние.''
<tex> r = (1, 2, ..., k); </tex>
<tex> p = (1, 2, ..., k); </tex>
<tex> t = (0, 0, ..., 0); </tex>
<tex> d = (-1, -1, ..., -1); </tex>
''Стандартный шаг.'' Увеличить вектор <tex>t</tex> на 1. При этом несколько младших разрядов получат нулевые значения, а в одном из разрядов, <tex>j</tex>-м, значение увеличится на 1 (при <tex>j = 1</tex> процесс заканчивается). Сменить направление движения всех элементов младше <tex>j</tex>-го, т.е. положить <tex>d_i</tex> для <tex>i > j </tex>. Поменять местами <tex>j</tex>-й элемент и соседний и соседний с ним (если <tex>d_j = -1</tex> - левый, иначе - правый).
[[Файл:123.png]]
Элемент <tex>j</tex> стоит на месте <tex>s = p_i</tex>. Это значит, что <tex>r_s = j</tex>. Соседнее место - это <tex>s' = p_i + d_j</tex>. На нем стоит какой-то элемент <tex>j' = r_s' </tex>. Поменять местами в перестановке элементы <tex>j</tex> и <tex>j'</tex> означает поменять местами содержимое <tex>p_i</tex> и <tex>p_j'</tex>, a также <tex>r_s</tex> и <tex>r_s'</tex>.
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
