Коды Грея для перестановок

Материал из Викиконспекты
Версия от 07:41, 10 ноября 2011; 192.168.0.2 (обсуждение) (Сведение задачи построение кода Грея для перестановок к графам)
Перейти к: навигация, поиск
код Грея для перестановки при n = 2
1 2
2 1
код Грея для перестановки при n = 3
1 2 3
2 1 3
2 3 1
3 2 1
3 1 2
1 3 2
код Грея для перестановки при n = 4
1 2 3 4 
2 1 3 4 
2 3 1 4 
2 3 4 1 
3 2 4 1 
3 2 1 4 
3 1 2 4 
1 3 2 4 
1 3 4 2 
3 1 4 2 
3 4 1 2 
3 4 2 1 
4 3 2 1 
4 3 1 2 
4 1 3 2 
1 4 3 2 
1 4 2 3 
4 1 2 3 
4 2 1 3 
4 2 3 1 
2 4 3 1 
2 4 1 3 
2 1 4 3 
1 2 4 3 

Определение

Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.

Элементарной транспозицией называют транспозиция двух соседних элементов, то есть обмен местами двух соседних элементов.

Построения Кода Грея для перестановок

Строим из рекурсивных соображений. При фиксированной перестановке из [math]k - 1[/math] элемента можно перебрать все [math]k[/math] вариантов добавления к этой перестановке элемента [math]k[/math], и этот перебор можно осуществить передвигая элемент [math]k[/math] каждый раз на соседнее место, Например

3652147 -> 3652174 -> 3652714 -> 3657214 и т. д.

На фоне перебора позиций [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] то место [math]p_i[/math], на котором стоит [math]i[/math] стоит в перестановке [math]r[/math].

Начальное состояние.
[math] r = (1, 2, ..., k); [/math]
[math] p = (1, 2, ..., k); [/math]
[math] t = (0, 0, ..., 0); [/math]
[math] d = (-1, -1, ..., -1); [/math]

Стандартный шаг. Увеличить вектор [math]t[/math] на 1. При этом несколько младших разрядов получат нулевые значения, а в одном из разрядов, [math]j[/math]-м, значение увеличится на 1 (при [math]j = 1[/math] процесс заканчивается). Сменить направление движения всех элементов младше [math]j[/math]-го, т.е. положить [math]d_i[/math] для [math]i \gt j [/math]. Поменять местами [math]j[/math]-й элемент и соседний и соседний с ним (если [math]d_j = -1[/math] - левый, иначе - правый).

[math] i [/math] [math] t [/math] [math] d [/math] [math] p [/math] [math] r [/math] [math] j [/math] Комментарии
1 0000 ---- 1234 1234 - Здесь [math] j [/math] не определено
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 -+-- - - 1 Остановка процесса


Элемент [math]j[/math] стоит на месте [math]s = p_i[/math]. Это значит, что [math]r_s = j[/math]. Соседнее место - это [math]s' = p_i + d_j[/math]. На нем стоит какой-то элемент [math]j' = r_s' [/math]. Поменять местами в перестановке элементы [math]j[/math] и [math]j'[/math] означает поменять местами содержимое [math]p_i[/math] и [math]p_j'[/math], a также [math]r_s[/math] и [math]r_s'[/math].

Сведение задачи построение кода Грея для перестановок к графам

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам [math]f[/math] и [math]g[/math], соединены ребром, если [math]g[/math] образуется из [math]f[/math] однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.

См. также

Литература

Романовский, И.В. Дискретный Анализ - Санкт-Петербург 2003 стр. 39-41