130
правок
Изменения
Нет описания правки
Таким образом получаем для каждой перестановки длиной <tex>k - 1</tex> (всего <tex>(k - 1)!</tex> штук) по <tex>k</tex> новых перестановок, в сумме <tex>k\cdot(k - 1)! = k!</tex> перестановок. Все они различны, так как для любых двух перестановок из нового кода Грея элемент <tex>k</tex> стоит на разных позициях,а если <tex>k</tex> стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной <tex>k - 1</tex>. Так же все соседние перестановки отличаются ровно в одной элементарной транспозиции. Итого, мы получили список из <tex>k!</tex> различных перестановок длиной <tex>k</tex>, причём соседние отличаются в одной элементарной транспозиции.
== Примеры кодов Грея для перестановок ==
'''Перестановки для n = 2'''
{| style="background-color:#CCC;margin:0.5px"
|}
'''Перестановки для n = 3'''(подчёркнуты пары переставляемых элементов)
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Номер
|style="background-color:#FFF;padding:2px 30px"|
|}
== Псевдокод получения кода Грея ==
Получаем код Грея рекурсивно, в базовом случае <tex>n = 1</tex> возвращаем список из одной перестановки <tex>\{1\}</tex>.
'''list<list<int>>''' gray_code(n):
'''if''' n == 1
'''return''' [{1}] <font color=darkgreen> //возращаем список из одной перестановки</font color=darkgreen>
'''else'''
'''list<list<int>>''' result = [] <font color=darkgreen> //пустой список</font color=darkgreen>
'''list<list<int>>''' perms = gray_code(n - 1) <font color=darkgreen> //perms {{---}} перестановки из n - 1 элемента</font color=darkgreen>
'''bool''' backward = ''false'' <font color=darkgreen> //переменная которая говорит с какой стороны заполнять перестановку</font color=darkgreen>
'''for''' perm '''in''' perms <font color=darkgreen> //perm {{---}} текущая перестановка</font color=darkgreen>
'''if''' backward
'''list<int>''' current = concat(perm, {n})<font color=darkgreen> //дописываем {n} в конец perm</font color=darkgreen>
result.append(current)<font color=darkgreen> //добавляем в ответ перестановку current</font color=darkgreen>
'''for''' i = n '''downto''' 2
swap(current[i - 1], current[i])<font color=darkgreen> //переставляем n</font color=darkgreen>
result.append(current) <font color=darkgreen> //добавляем в ответ перестановку current</font color=darkgreen>
'''else'''
'''list<int>''' current = concat({n}, perm) <font color=darkgreen> //дописываем {n} в начало perm</font color=darkgreen>
result.append(current) <font color=darkgreen> //добавляем в ответ перестановку current</font color=darkgreen>
'''for''' i = 1 '''to''' n - 1
swap(current[i], current[i + 1]) <font color=darkgreen> //переставляем n</font color=darkgreen>
result.append(current) <font color=darkgreen> //добавляем в ответ перестановку current</font color=darkgreen>
backward = '''not''' backward <font color=darkgreen> //меняем состояние backward</font color=darkgreen>
'''return''' result <font color=darkgreen> //возвращаем ответ в виде списка</font color=darkgreen>
== Реализация в нерекурсивном виде. Алгоритм Джонсона-Троттера ==
