152
правки
Изменения
→Построения Кода Грея для перестановок
<tex> p = (1, 2, ..., k); </tex>
<tex> t = (0, 0, ..., 0); </tex>
<tex> d = (2-1, 2-1, ..., 2-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 = 2-1</tex> - левый, иначе - правый).
{| class = "standard" border = "1"
!i|t|d|p|r|j|Комментарии
|-
!1|0000|2222---- |1234|1234| - |Здесь J не определено |- !2 |0001 | ---- |1243 |1243 | 4 |Начинается движение эл. 4 |- !3 |0002 | ---- |1342 |1423 | 4 | |- !4 |0003 | ---- |2341 |4123 | 4 | |- !5 |0010 | ---+ |2431 |4132 | 3 |Шаг эл. 3, у 4 смена направления|- !6 |0011 | ---+ |1432 |1432 | 4 | |- !7 |0012 | ---+ |1423 |1342 | 4 | |- !8 |0013 | ---+ |1324 |1324 | 4 | |- !9|0020| ----|2314|3124|3|Второй шаг эл. 3|- !10|0021| ----|2413|3142|4||- !11|0022| ----|3412|3412|4||- !12|0023| ----|3421|4312|4| |- !13|0100| --++|4321|4321|2|Шаг эл. 2. Смена направлений у эл. 3 и эл. 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| -+--| -
| -
|Здесь J не определено1|Остановка процесса
|-
}
Элемент <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>.
