94
правки
Изменения
Нет описания правки
Получим $k$ различных перестановок, отличающихся одной элементарной транспозицией. Возьмем следующую строку из кода Грея для перестановок длиной $n = k - 1$, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):
$\{'''a<sub>2</sub>'''a_2, '''a<sub>1</sub>'''a_1, a<sub>3</sub>a_3, ...\dots, a<sub>a_{k - 1</sub>}\}$
Элемент $a_{k}$ записываем в конец и начинаем "двигать" его влево:
*$\{a<sub>2</sub>a_2, a<sub>1</sub>a_1, a<sub>3</sub>a_3, ...\dots, a<sub>\underline{a_{k - 1</sub>}, a<sub>k</sub>} \}$ (4)*$\{a<sub>2</sub>a_2, a<sub>1</sub>a_1, a<sub>3</sub>a_3, ...\underline{\dots, '''a<sub>k</sub>'''}, '''a<sub>a_{k - 1</sub>'''}\}$*..........................*$\{a<sub>2</sub>a_2, a<sub>1</sub>a_1, a<sub>3</sub>\underline{a_3, '''a<sub>k</sub>'''}, ...\dots, a<sub>a_{k - 1</sub>}\}$*$\{a<sub>2</sub>a_2, a<sub>1</sub>\underline{a_1, '''a<sub>k</sub>'''}, '''a<sub>3</sub>'''a_3, ...\dots, a<sub>a_{k - 1</sub>}\}$*$\{a<sub>2</sub>\underline{a_2, '''a<sub>k</sub>'''}, '''a<sub>1</sub>'''a_1, a<sub>3</sub>a_3, ...\dots, a<sub>a_{k - 1</sub>}\}$*$\{'''a<sub>k</sub>''', '''a<sub>2</sub>'''a_2, a<sub>1</sub>a_1, a<sub>3</sub>a_3, ...\dots, a<sub>a_{k - 1</sub>}\}$
Опять получили $k$ различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея для перестановок длиной $n = k - 1$, записываем в ее начало элемент $a_{k}$ и двигаем его вправо, как для первой перестановки и т.д.
{1, 2}
Тогда следуя алгоритму полученный код будет выглядеть так (жирным выделены элементы, которые поменялисьподчёркнуты пары переставляемых элементов):
* $\{\underline{3, 2}, 1\} $ {{---}} берем первую перестановку и добавляем в начало тройку* $\{'''2''', '''\underline{3''', 1} \}$ {{---}} двигаем до последней позиции* $\{\underline{2, '''1'''}, '''3'''\}$* $\{'''1''', '''\underline{2''', 3} \}$ {{---}} берем следующую перестановку и записываем тройку в конец* $\{\underline{1, '''3'''}, '''2'''\} $ {{---}} двигаем в начало* $\{'''3''', '''1''', 2\}$
Код Грея получен.
