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

код Грея для перестановки при 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]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] однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.

См. также

• Коды Грея
• Комбинаторные объекты
• Гамильтонов путь

[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	Остановка процесса