Изменения

{{Определение|definition ='''Элементарная транспозиция''' (англ. ''Adjacent transposition'') {{---}} перестановка местами двух соседних элементов.}} '''Коды Грея для перестановок'''(англ. ''Gray code for permutation'') {{---}} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией. '''Элементарная транспозиция'''(англ. Adjacent transposition) — перестановка местами двух соседних элементов.

|style="background-color:#FFF;padding:2px 30px"| <tex>\{2, 1, 2\} </tex>

|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, 2, 1\} </tex>

'''Перестановки для n = 3'''(подчёркнуты пары переставляемых элементов)

|style="background-color:#FFF;padding:2px 30px"| <tex>\{1\underline{3, 2}, 31\} </tex>|style="background-color:#FFF;padding:2px 30px"| берем первую перестановку и добавляем в начало тройку

|style="background-color:#FFF;padding:2px 30px"| <tex>\{12, \underline{3, 21}\} </tex>|style="background-color:#FFF;padding:2px 30px"| двигаем до последней позиции

|style="background-color:#FFF;padding:2px 30px"| <tex>\{3\underline{2, 1}, 23\}</tex>|style="background-color:#FFF;padding:2px 30px"|

|style="background-color:#FFF;padding:2px 30px"| <tex>\{31, \underline{2, 13}\}</tex>|style="background-color:#FFF;padding:2px 30px"| берем следующую перестановку и записываем тройку в конец

|style="background-color:#FFF;padding:2px 30px"| <tex>\{2\underline{1, 3}, 12\} </tex>|style="background-color:#FFF;padding:2px 30px"| двигаем в начало

|style="background-color:#FFF;padding:2px 30px"| <tex>\{23, 1, 32\} </tex>|style="background-color:#FFF;padding:2px 30px"|

Сопоставим каждому элементу перестановки <tex>p[i]</tex> направление <tex>d[i]</tex>. Будем указывать направление при помощи стрелок '''←''' ("влево") или '''→'''("вправо"). Назовём элемент подвижным, если по направлению стелки стрелки стоит элемент меньше его. Например, для <tex> p = \{1, 3, 2, 4, 5\},\;d = \{\leftarrow, \to, \leftarrow, \to, \leftarrow\}</tex>, подвижными являются элементы <tex>3 </tex> и <tex>5</tex>. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. Изначально <tex> p = \{1, \dots ,n\},\;d = \{\leftarrow, \dots ,\leftarrow\}</tex>.

*<tex> p = \{1, 2, \textbf{3}\}\;\;\;d = \{</tex>←\leftarrow, ←\leftarrow, ←<tex>\leftarrow\}</tex>*<tex> p = \{1, \textbf{3}, 2\}\;\;\;d = \{</tex>←\leftarrow, ←\leftarrow, ←<tex>\leftarrow\}</tex>*<tex> p = \{3, 1, \textbf{2}\}\;\;\;d = \{</tex>←\leftarrow, ←\leftarrow, ←<tex>\leftarrow\}</tex>*<tex> p = \{\textbf{3}, 2, 1\}\;\;\;d = \{</tex>→\to, ←\leftarrow, ←<tex>\leftarrow\}</tex>*<tex> p = \{2, \textbf{3}, 1\}\;\;\;d = \{</tex>←\leftarrow, →\to, ←<tex>\leftarrow\}</tex>*<tex> p = \{2, 1, 3\}\;\;\;d = \{</tex>←\leftarrow, ←\leftarrow, →<tex>\to\}</tex>

'''list'''< '''list'''<'''int>>'''> > gray_code(n): '''list'''<'''int>'''> perm = {1, ... , n} '''list'''<'''char>'''> dir = {←, ... , ←} '''list'''< '''list'''<'''int>>'''> > result '''while''' (''true)''

'''for''' (i = 1 '''to''' n)

'''for''' (i = 1 '''to''' n){

*<tex>(\overset{\text {$\to$}}{a,}</tex> ←<tex>)</tex> <tex> {{--- </tex> }} элемент с заданным направлением(компонента).*<tex>P[i]</tex> <tex> {{--- </tex> }} перестановка с номером <tex>i</tex>.*<tex>P[i]\backslash\{a\}\;</tex> <tex> {{--- </tex> }} перестановка с номером <tex>i</tex> без элемента <tex>a</tex>.

|statement=Число <tex>n</tex> в перестановке не является подвижным элементом тогда и только тогда, когда первая компонента перестановки есть <tex>(\overset{\text {$\leftarrow$}}{n,</tex> ←<tex>)}</tex> или последняя компонента есть <tex>(\overset{\text {$\to$}}{n,</tex> →<tex>)}</tex>.

|proof=Заметим, что если в перестановке есть подвижный элемент <tex>a \neq n</tex>, то после транспозиции его с соседним элемнтом(по направлению стрелки), нам нужно будет заменить направление стрелок у всех элементов больше <tex>a</tex>. Так как <tex>n</tex> больше любого элемента из перестановки, то направление стрелки у него тоже изменится. По нашему утверждению, либо в новой перестановке окажется компонента <tex>(\overset{\text {$\to$}}{n,</tex> →<tex>)}</tex> на первой позиции, либо компонента <tex>(\overset{\text {$\leftarrow$}}{n,</tex> ←<tex>)}</tex> на последней позиции. В обоих случаях <tex>n</tex> окажется подвижным элементом в следующих <tex>n</tex> перестановках. Так как в следующих <tex>n</tex> перестановках подвижным элементом будет только <tex>n</tex>, то <tex>P[i + 1]\backslash\{n\} = P[i + 2]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>.

Поговорим об асиптотике. Снова разобьём наши перестановки на блоки по <tex>n</tex> элементов. Немного модифицируем алгоритм. Заметим, что в каждом блоке нам нужно искать максимальный элемент только один раз. В остальных случаях этим элементом будет <tex>n</tex>. Следовательно, менять направление стрелок нужно тоже только один раз(в остальных случаях менять направления не нужно, так как <tex>n</tex> - подвижный элемент, а менять направление стрелок нужно только у бóльших элементов). Следовательно, блок выполняется за <tex>O(n) + O(n) + O(n) = O(n)</tex>. Всего блоков <tex> -\:(n - 1)!</tex>. Общая асимптотика <tex>O(n) * \cdot (n - 1)! = O(n!)</tex>.

Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из <tex>n - 1</tex> элемента), а только текущую. Следовательно, этот алгоритм потребляет только <tex>O(n)</tex> памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее. Это можно строго доказать ===Интересный факт===Существует более общая формулировке задачи {{---}} для двух соседних перестановок должно выполняться, но доказательство довольно громозодкое и приводить его мы здесь что позиции одинаковых чисел в них отличаются не будемболее, чем на единицу.Для этой формулировки верно, что для любой перестановки <tex>u</tex> число различных перестановок <tex>v</tex>, которые могут стоять после <tex>u</tex>, равно <tex>n + 1</tex> числу Фибоначчи. Этот факт был открыт студентом нашего университета.