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

код Грея для перестановки при 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] - левый, иначе - правый).

i	t	d	p	r	j	Комментарии
	1	0000	----	1234	1234	-	Здесь J не определено		2	0001	----	1243	1243	4	Начинается движение эл. 4	} Элемент [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] однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. См. также Коды Грея Комбинаторные объекты Гамильтонов путь