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

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

См. также

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