== '''Построения Кода Грея для перестановок''' ==
Строим из рекурсивных соображенийЧтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1. При фиксированной перестановке из <tex>k - Для n = 1</tex> элемента можно перебрать все <tex>k</tex> вариантов добавления к этой перестановке элемента <tex>k</tex>, и этот перебор можно осуществить передвигая элемент <tex>k</tex> каждый раз на соседнее место, Напримергод Грея выглядит так:
365214'''7''' {1} -> 36521'''7'''4 -> 3652'''7'''14 -> 365'''7'''214 и т. дn! различных перестановок отличных друг от друга в одной транспозиции (очевидно).
На фоне перебора позиций <tex>Будем строить код Грея для перестановок длины n = k. Предположим, что нам известен код Грея для перестановок длиной n = k</tex>-го элемента должны проводиться переборы перестановок меньшего порядка, к которым применяется тот же принцип, т1.е., например в нашем случае после получения набора 7365214 требуется сдвинуть влево или вправо элемент 6Возьмем первую перестановку из нам известного кода.Пусть она выглядит так:
Действовать будем так{a1, a2, a3, . Каждые <tex>k .., ak- 1</tex> итерации будем давать команду на сдвиг <tex>k</tex>-го элемента} ,где ai при i = 1, а затем менять направление движения его на противоположное и будем давать команду на сдвиг элемента с меньшим номером; для этих выделенных итераций нужно делать то же самое: на <tex>k - 2</tex> из них двигать <tex>(, 3, ..., k - 1)</tex>-й элемент, а на <tex>(k - 1)</tex>-й итерации сменить ему направление движения, и т.дэлементы перестановки.
Построение. Кроме рабочей Элемент ak запишем в начало этой перестановки <tex>r</tex> и её номера в факториальной системе <tex>t</tex> (младший разряд - последний) потребуется иметь массив <tex>d</tex>, задающий текущее направления движения всех элементов. Удобно еще иметь массив, сопоставляющий каждому элементу <tex>i</tex> то место <tex>p_i</tex>, на котором стоит <tex>i</tex> стоит в перестановке <tex>r</tex>.:
''Начальное состояние.'' <br><tex> r = (1, 2, ..., k); </tex><br><tex> p = (1{ak, 2a1, ...a2, k); </tex><br><tex> t = (0, 0, ..., 0); </tex><br><tex> d = (-1, -1a3, ..., ak -1); </tex><br>}
''Стандартный шаг.'' Увеличить вектор <tex>t</tex> на 1. При этом несколько младших разрядов получат нулевые значения, а в одном из разрядов, <tex>j</tex>-м, значение увеличится на 1 (при <tex>j = 1</tex> процесс заканчивается). Сменить направление движения всех элементов младше <tex>j</tex>-гоБудем "двигать" этот элемент ak влево, т.е. положить <tex>d_i</tex> для <tex>i > j </tex>. Поменять местами <tex>j</tex>-й элемент и соседний и соседний меняя его с ним (если <tex>d_j = -1</tex> - левый, иначе - правый).<br>соседним:
{|class = "standard" border = "ak, a1, a2, a3, ..., ak - 1} (1")!<tex> i </tex> {a1, ak, a2, a3, ..., ak - 1} (2)|<tex> t </tex> {a1, a2, ak, a3, ..., ak - 1}|<tex> d </tex>{a1, a2, a3, ak, ..., ak - 1}|<tex> p </tex> ..........................|<tex> r </tex> |<tex> j </tex> {a1, a2, a3, ..., ak, ak - 1}|Комментарии |{a1, a2, a3, ..., ak -1, ak} (3)
!Получим k различных перестановок, отличающихся в одной транспозиции. Возьмем следующую строку из кода Грея для перестановок длиной n = k - 1, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1 |0000 | ---- |1234 |1234 | - |Здесь <tex> j </tex> не определено |-), (2), то и во второй перестановке первый элемент "поменяется" со вторым):
!2 |0001 | ---- |1243 |1243 | 4 |Начинается движение эл{a2, a1, a3, ... 4 |, ak -1}
!3 |0002 | ---- |1342 |1423 | 4 | |-Элемент ak записываем в конец и начинаем "двигать" влево, меняя его с правостоящим:
!{a2, a1, a3, ..., ak - 1, ak} (4 )|0003 | ---{a2, a1, a3, ..., ak, ak - 1}|2341 ..........................|4123 {a2, a1, a3, ak, ..., ak - 1}| 4 {a2, a1, ak, a3, ..., ak - 1}| {a2, ak, a1, a3, ..., ak - 1}|{ak, a2, a1, a3, ..., ak -1}
!5 |0010 | Опять получили k различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной n = k ---+ |2431 |4132 | 3 |Шаг эл1, записываем в ее начало элемент ak и двигаем его вправо, как для первой перестановки и т.д. 3, у 4 смена направления|-
!6 |0011 | Для каждой перестановки длиной n = k -1 (всего их (k --+ |1432 |1432 | 4 | |- 1)!7 |0012 | ---+ |1423 |1342 | 4 | |- !8 |0013 | ---+ |1324 |1324 | 4 | |- !9|0020| ----|2314|3124|3|Второй шаг эл) мы получили k новых перестановок. 3|Итого k•(k - 1)!10|0021| ----|2413|3142|4||- !11|0022| ----|3412|3412|4||- = k!12|0023| ----|3421|4312|4| |- !13|0100| --++|4321|4321|2|Шаг элперестановок. 2Все они различны, т. Смена направлений у элк. 3 для любых двух перестановок из нового кода Грея ak стоит на разных позициях,а если ak стоит на одной и элтой же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1. 4.|- !14|0101| --++|4312|3421|4||- !15|0102| --++|4213|3241|4||- !16|0103| -Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок -++|3214|3214|4||- !17|0110| --+-|3124|2314|3||- !18|0111| --+-|4123|2341|4||- !19|0112| --+-|4132|2431|4||- !20|0113| --+-|4231|4231|4||- !21|0120| --++|3241|4213|3||- !22|0121| --++|3124|2413|4||- !23|0122| --++|2143|2143|4||- !24|0123| --++|2134 |2134|4||- !25|1000| -+--| -| -|1|Остановка процесса|} <br>Элемент <tex>j</tex> стоит имеют ak на месте <tex>s = p_i</tex>одной и той же позиции, но отличаются в одной транспозиции, т. Это значит, что <tex>r_s = j</tex>к. Соседнее место - это <tex>s' является перестановками в коде Грея для перестановок длиной n = p_i + d_j</tex>. На нем стоит какойk -то элемент <tex>j' = r_s' </tex>1). Поменять местами Таким образом мы получили k! различных перестановок длиной k, отличающихся в перестановке элементы <tex>j</tex> и <tex>j'</tex> означает поменять местами содержимое <tex>p_i</tex> и <tex>p_j'</tex>, a также <tex>r_s</tex> и <tex>r_s'</tex>одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
