Изменения
Нет описания правки
|-
| <span style="font-size:smaller;">код Грея для перестановки при n = 2</span>
2 1
1 2
|-
| <span style="font-size:smaller;">код Грея для перестановки при n = 3</span>
3 2 1
2 3 1
2 1 3
1 2 3
3 1 2
|-
| <span style="font-size:smaller;">код Грея для перестановки при n = 4</span>
4 3 2 1 3 4 2 1 3 2 4 1 3 2 1 3 4 2 3 1 4 2 3 4 1 3 2 4 3 1 4 2 3 1 4 2 1 4 3 3 1 2 4 1 3 2 1 4 3 2 4 2 1 3 4 2 1 2 3 1 4 2 3 4 1 2 4 3 3 1 4 2 1 4 3 2 1 4 3 1 2 3 4 1 3 2 1 4 3 2 1 3 4 2 3 4 1 3 2 3 4 2 1 3 4 2 3 1 2 4 2 4 3 1 4 2 2 3 4 1 3 2 2 1 4 3 1 2 4 3
|}
<wikitex>
== '''Определение''' ==
'''Коды Грея для перестановок''' - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.
'''Элементарной транспозициейЭлементарная транспозиция''' называют - транспозиция двух соседних элементов, то есть обмен местами двух соседних элементов. == '''Построения кода Грея для перестановок''' ==
Чтобы построить код Грея для перестановки длиной n будем использовать код Грея для перестановки длиной n - 1.
Для n = 1 год Грея выглядит так:
{1} --- n! различных перестановок отличных друг от друга в одной транспозиции (очевидно).
{a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ..., a<sub>k-1</sub>} ,где a<sub>i</sub> при i = 1, 2, 3, ..., k --- элементы перестановки.
Для каждой перестановки длиной n = k - 1 (всего их (k - 1)!) мы получили k новых перестановок. Итого k•k(k - 1)! = k! перестановок. Все они различны, т.к. для любых двух перестановок из нового кода Грея a<sub>k</sub> стоит на разных позициях,а если a<sub>k</sub> стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной n = k - 1(см. (3), (4)). Так же все соседние перестановки отличаются ровно в одной транспозиции (образованные от одной перестановки различны благодаря построению, от разных перестановок --- имеют a<sub>k</sub> на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной n = k - 1, см (3), (4)). Таким образом мы получили k! различных перестановок длиной k, отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной n получен.
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
== Литература ==
Романовский, И.В. Дискретный Анализ - Санкт-Петербург 2003 стр. 39-41
<\wikitex>
