Изменения

{{Определение|definition ='''Элементарная транспозиция''' (англ. ''Adjacent transposition'') {{---}} перестановка местами двух соседних элементов.}} '''Коды Грея для перестановок''' (англ. ''Gray code for permutation'') {{---}} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.== Построение кода Грея для перестановок == Будем строить код Грея для длины <wikitextex>n = k</tex>. Предположим, что нам известен [[Коды Грея | код Грея]] для перестановок длиной <tex>k - 1</tex>. Возьмем первую перестановку из известного нам кода. Она имеет следующий вид: <tex>\{a_1, a_2, a_3, \dots, a_{k-1}\}</tex> Сначала запишем число <tex>k</tex> в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями (подчёркнуты пары переставляемых элементов).

{{Определение|definition='''Коды Получим <tex>k</tex> различных перестановок, отличающихся одной элементарной транспозицией. Возьмем следующую перестановку из кода Грея для перестановок''' длины <tex>k - 1</tex> и припишем в конце число <tex>k</tex>. Эта перестановка отличается на одну элементарную транспозицию (последние элементы совпадают, а префиксы длины <tex>k - 1</tex> отличаются на элементарную транспозицию). Пусть она имеет следующий вид: <tex>\{b_1, b_2,b_3, \dots, b_{k---1}\} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.<br/tex>

{| border="1" cellpadding="3" | $n = 2$ || $\{1Продолжаем аналогично. Для каждой перестановки дописываем <tex>k</tex> в один конец (поочерёдно), 2\}$ || $\{2и с помощью элементарных транспозиций двигаем в другой конец, 1\}$ |- | $n = 3$ || $\{1, 2, 3\}$ || $\{1, 3, 2\}$ || $\{3, 1, 2\}$ || $\{3, 2, 1\}$ || $\{2, 3, 1\}$ || $\{2, 1, 3\}$ |}при этом добавляя каждую промежуточную перестановку в список.

Таким образом получаем для каждой перестановки длиной <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 = k$2'''{| style="background-color:#CCC;margin:0. Предположим, что нам известен код Грея для перестановок длиной $k 5px"!style="background-color:#EEE"| Номер!style="background-color:#EEE"| Перестановка|-|style="background- color:#FFF;padding:2px 30px"| <tex>1$. Возьмем первую перестановку из известного нам кода. Она имеет следующий вид</tex>|style="background-color:#FFF;padding: $2px 30px"| <tex>\{a_1, a_2, a_32, 1\} </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\dots, a_{k-1, 2\}\</tex>|}$

Сначала запишем $k$ в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями '''Перестановки для n = 3''' (подчёркнуты пары переставляемых элементов){| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Номер!style="background-color:#EEE"| Перестановка!style="background-color:#EEE"| Пояснение|-|style="background-color:#FFF;padding:2px 30px"| <tex>1</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{3, 2}, 1\} </tex>|style="background-color:#FFF;padding:2px 30px"| берем первую перестановку и добавляем в начало тройку|-|style="background-color:#FFF;padding:2px 30px"| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{2, \underline{3, 1}\} </tex>|style="background-color:#FFF;padding:2px 30px"| двигаем до последней позиции |-|style="background-color:#FFF;padding:2px 30px"| <tex>3</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{2, 1}, 3\}</tex>|style="background-color:#FFF;padding:2px 30px"| |-|style="background-color:#FFF;padding:2px 30px"| <tex>4</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, \underline{2, 3}\}</tex>|style="background-color:#FFF;padding:2px 30px"| берем следующую перестановку и записываем тройку в конец |-|style="background-color:#FFF;padding:2px 30px"| <tex>5</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{1, 3}, 2\} </tex>|style="background-color:#FFF;padding:2px 30px"| двигаем в начало|-|style="background-color:#FFF;padding:2px 30px"| <tex>6</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{3, 1, 2\} </tex>|style="background-color:#FFF;padding:2px 30px"| |}

Получим $k$ различных перестановокПолучаем код Грея рекурсивно, отличающихся одной элементарной транспозицией. Возьмем следующую строку из кода Грея для перестановок длиной $в базовом случае <tex>n = k - 1$, которая будет выглядеть так (т.к. мы получили, что элемент стоящий на первом месте в перестановке будет "двигаться" вправо см</tex> возвращаем список из одной перестановки <tex>\{1\}</tex>. (1), (2), то и во второй перестановке первый элемент "поменяется" со вторым):

'''list<list<int>>''' gray_code(n): '''if''' n == 1 '''return''' [{1}] <font color=darkgreen> //возращаем список из одной перестановки</font color=darkgreen> '''aelse''' '''list<list<int>>''' result = [] <subfont color=darkgreen>2 //пустой список</subfont color=darkgreen> ''', list<list<int>>'''aperms = gray_code(n - 1) <subfont 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 {{---}} текущая перестановка</subfont color=darkgreen> '''if''' backward '''list<int>''' current = concat(perm, a{n})<subfont color=darkgreen>3 //дописываем {n} в конец perm</subfont 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.., aappend(current) <font color=darkgreen> //добавляем в ответ перестановку current<sub/font color=darkgreen>k '''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</subfont color=darkgreen> backward = '''not''' backward <font color=darkgreen> //меняем состояние backward</font color=darkgreen> '''return''' result <font color=darkgreen> //возвращаем ответ в виде списка</font color=darkgreen>}

Элемент $a_{k}$ записываем == Реализация в конец и начинаем "двигать" его влево:нерекурсивном виде. Алгоритм Джонсона-Троттера ==

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

Опять получили $k$ различных перестановок, отличающихся в одной транспозиции. Далее берем третью строку из кода Грея === Пример работы алгоритма для перестановок длиной $n = k - 3 ===*<tex> p = \{1, 2, \textbf{3}\}\;\;\;d = \{\leftarrow, \leftarrow, \leftarrow\}</tex>*<tex> p = \{1, \textbf{3}, 2\}\;\;\;d = \{\leftarrow, \leftarrow, \leftarrow\}</tex>*<tex> p = \{3, 1$, записываем в ее начало элемент $a_\textbf{k2}$ и двигаем его вправо\}\;\;\;d = \{\leftarrow, как для первой перестановки и т.д.\leftarrow, \leftarrow\}</tex>*<tex> p = \{\textbf{3}, 2, 1\}\;\;\;d = \{\to, \leftarrow, \leftarrow\}</tex>*<tex> p = \{2, \textbf{3}, 1\}\;\;\;d = \{\leftarrow, \to, \leftarrow\}</tex>*<tex> p = \{2, 1, 3\}\;\;\;d = \{\leftarrow, \leftarrow, \to\}</tex>

Для каждой перестановки длиной $n = k - == Псевдокод ===<code> <font color=darkgreen>//Элементы нумеруются начиная с 1$ </font color=darkgreen> '''list<list<int>>''' gray_code(всего их $(k - n): '''list<int>''' perm = {1)!$) мы получили $k$ новых перестановок, ... Итого $k\cdot(k - 1)! , n} '''list<char>''' dir = k!$ перестановок{←, . Все они различны, т.к. для любых двух перестановок из нового кода Грея элемент $a_{k}$ стоит на разных позициях,а если $a_{k←}$ стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной $n '''list<list<int>>''' result '''while''' ''true'' result.append(perm); <font color=darkgreen> //добавляем в ответ текущую перестановку</font color=darkgreen> '''int''' id = k - 1$ ; <font color=darkgreen> //индекс наибольшего подвижного элемента </font color=darkgreen> '''for''' i = 1 '''to''' n '''if''' (perm[i] - подвижный) '''and''' (см. (3id == -1), '''or''' (4perm[i] > perm[id])). Так же все соседние перестановки отличаются ровно в одной транспозиции id = i '''if''' (образованные от одной перестановки различны благодаря построению, от разных перестановок {{id == ---}} имеют $a_{k}$ на одной и той же позиции, но отличаются в одной транспозиции, т.к. является перестановками в коде Грея для перестановок длиной $n 1) '''break''' <font color=darkgreen> //не нашли подвижного элемента</font color=darkgreen> '''for''' i = k - 1$, см '''to''' n '''if''' (3perm[i] > perm[id]), reverse(4dir[i])<font color=darkgreen> //меняем направление стрелки</font color=darkgreen> swap(id). Таким образом мы получили $k!$ различных перестановок длиной $k$<font color=darkgreen> //меняем элемент perm[id], отличающихся в одной транспозиции. Алгоритм для построения кодов Грея для перестановок длиной $n$ получен.dir[id] c элементом по направлению стелки</font color=darkgreen> '''return''' result </code>

== Пример применения алгоритма = Доказательство корректности ===Очевидно, что требование о том, что каждая генерируемая перестановка отличается от предыдущей транспозицией двух соседних элементов выполнено исходя из самого алгоритма. Осталось доказать, что таким образом мы сгенерируем все перестановки.

Рассмотрим код Грея для длины Будем использовать обозначения:*<tex>\overset{\text {$n = 2\to$:}}{a}</tex> {{---}} элемент с заданным направлением(компонента).*<tex>P[i]</tex> {{---}} перестановка с номером <tex>i</tex>.*<tex>P[i]\backslash\{a\}\;</tex> {{---}} перестановка с номером <tex>i</tex> без элемента <tex>a</tex>.

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

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

Код Грея полученТеперь докажем основную лемму.{{Лемма|id=lemma2|statement=Алгоритм Джонсона-Троттера строит все перестановки из <tex>n</tex> элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.|proof=Доказывать будем по индукции. Для <tex>n = 1\; - </tex> очевидно. Предположим, что для <tex>n - 1</tex> алгоритм строит перестановки корректно. Докажем, что алгоритм будет корректно строить перестановки и для <tex>n</tex> элементов. Разобьём все <tex>n!</tex> перестановок на блоки по <tex>n</tex> (подряд). В силу вышедоказанной леммы в каждом блоке <tex>P[i]\backslash\{n\} = P[i + 1]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>, если <tex>i\; - </tex> начало группы. Значит, в каждой группе какая-то перестановка из <tex>n - 1</tex> элемента дополняется до перестановки из <tex>n</tex> всеми возможными способами. Теперь докажем, что на переход между блоками элемент <tex>n</tex> никак не влияет. Заметим, что при переходе между блоками <tex>n</tex> является неподвижным элементом. В силу нашего утверждения <tex>n</tex> стоит либо на первой, либо на последней позиции. Так как <tex>n</tex> больше любого элемента, то никакой подвижный элемент не может указывать на <tex>n</tex>. В силу этих фактов <tex>n</tex> никак не повлияет на переход между блоками.Из этого можно сделать вывод, что при переходе между блоками перестановки строятся так же, как и перестановки из <tex>n - 1</tex> элемента, а каждая такая перестановка дополняется до перестановки из <tex>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> элемента), а только текущую. Следовательно, записанный в массив prev_perm[i]этот алгоритм потребляет только <tex>O(jn)</tex> памяти. Также, где $i$ из- номер перестановки, $j$ - номер элемента этой перестановки (номерация начинается с единицы)за нерекурсивности этот алгоритм работает быстрее.

t := false; {булевская переменная отвечающая за порядок перебора true: от начала к концу false: от конца к началу} for i := 1 to (n - 1)! do {перебираем все прошлые перестановки} if t = true thenИнтересный факт=== begin insert(prev_perm[i], t); Существует более общая формулировке задачи {{вставляем в конец, если t = true} writeln(prev_perm[i]); for j := 1 to n - 1 do {для каждой перестановки делаем n - 1 транспозиций-} begin swap(prev_perm[i](j), pred_perest[i](j + 1)); {меняем j и j + 1 элементы местами} t := false; writeln(prev_perm[i]); end; end else begin insert(prev_perm[i]для двух соседних перестановок должно выполняться, t); {вставляем что позиции одинаковых чисел в началоних отличаются не более, если t = false}чем на единицу. writeln(prev_perm[i]); for j := Для этой формулировки верно, что для любой перестановки <tex>u</tex> число различных перестановок <tex>v</tex>, которые могут стоять после <tex>u</tex>, равно <tex>n - 1 downto 1 do begin swap(prev_perm[i](j), prev_perm[i](j + 1)); {меняем j и j + 1 элементы местами} t := true; writeln(prev_perm[i]); end;</tex> числу Фибоначчи. end;Этот факт был открыт студентом нашего университета.

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть [[Основные_определения_теории_графов | граф]], вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам $<tex>f$ </tex> и $<tex>g$</tex>, соединены ребром, если $<tex>g$ </tex> образуется из $<tex>f$ </tex> однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.

* [[NP-полнота_задач_о_гамильтоновом_цикле_и_пути_в_графах | Гамильтонов путь]] == Литература Источники информации ==* Романовский, И.В. Дискретный Анализ - Санкт-Петербург , 2003 . - стр. 39-41- ISBN 5-94157-330-8* Федоряева Т.И. Комбинаторные алгоритмы - Новосибирск, 2011. - стр. 36-46 - ISBN 978-5-4437-0019-9* Ананий Левитин, Алгоритмы. Введение в разработку и анализ - Москва. Санкт-Петербург. Киев, 2006. - стр. 226 - 229 - ISBN 5-8459-0987-2[[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]