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