Изменения

{{Определение| widthdefinition ='''Элементарная транспозиция''' (англ. ''Adjacent transposition'') {{---}} перестановка местами двух соседних элементов.}} '''Коды Грея для перестановок''' (англ. ''Gray code for permutation'') {{---}} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.== Построение кода Грея для перестановок == Будем строить код Грея для длины <tex>n = k</tex>. Предположим, что нам известен [[Коды Грея | код Грея]] для перестановок длиной <tex>k - 1</tex>. Возьмем первую перестановку из известного нам кода. Она имеет следующий вид: <tex>\{a_1, a_2, a_3, \dots, a_{k-1}\}</tex> Сначала запишем число <tex>k</tex> в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями (подчёркнуты пары переставляемых элементов). * <tex>\{\underline{k, a_1}, a_2, a_3, \dots, a_{k-1}\}</tex>* <tex>\{a_1, \underline{k, a_2}, a_3, \dots, a_{k-1}\}</tex>* <tex>\{a_1, a_2, \underline{k, a_3}, \dots, a_{k-1}\}</tex>* <tex>\{a_1, a_2, a_3, \underline{k, \dots}, a_{k-1}\}</tex>* <tex>\{a_1, a_2, a_3, \dots, \underline{k, a_{k-1}}\}</tex>* <tex>\{a_1, a_2, a_3, \dots, a_{k-1}, k\}</tex> Получим <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}\}</tex> Элемент <tex>k</tex> записываем в конец и начинаем "двигать" его влево: * <tex>\{b_1, b_2, b_3, \dots, \underline{b_{k-1}, k}\}</tex>* <tex>\{b_1, b_2, b_3, \underline{\dots, k}, b_{k-1}\}</tex>* <tex>\{b_1, b_2, \underline{b_3, k}, \dots, b_{k-1}\}</tex>* <tex>\{b_1, \underline{b_2, k}, b_3, \dots, b_{k-1}\}</tex>* <tex>\{\underline{b_2, k}, b_1, b_3, \dots, b_{k-1}\}</tex>* <tex>\{k, b_1, b_2, b_3, \dots, b_{k-1}\}</tex> Продолжаем аналогично. Для каждой перестановки дописываем <tex>k</tex> в один конец (поочерёдно), и с помощью элементарных транспозиций двигаем в другой конец, при этом добавляя каждую промежуточную перестановку в список. Таким образом получаем для каждой перестановки длиной <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"!style="background-color:#EEE"| Номер!style="background-color:#EEE"| Перестановка|-|style="150background-color:#FFF;padding:2px 30px" align| <tex>1</tex>|style="rightbackground-color:#FFF;padding:2px 30px" cellpadding| <tex>\{2, 1\} </tex>|-|style="5background-color:#FFF;padding:2px 30px" border| <tex>2</tex>|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, 2\} </tex>|} '''Перестановки для n = 3''' (подчёркнуты пары переставляемых элементов){| style=" background-color:#CCC;margin:0.5px"!style="borderbackground-collapsecolor: collapse#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"| берем первую перестановку и добавляем в начало тройку

| <span style="fontbackground-sizecolor:smaller#FFF;padding:2px 30px"| <tex>код Грея для перестановки при n = 2</spantex> |style="background-color:#FFF;padding:2px 30px"| <tex>\{2, \underline{3, 1 2}\} </tex> 2 1|style="background-color:#FFF;padding:2px 30px"| двигаем до последней позиции

| <span style="fontbackground-sizecolor:smaller#FFF;padding:2px 30px"| <tex>код Грея для перестановки при n = 3</spantex> 1 2 3 |style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{2 , 1 }, 3\}</tex> 2 3 1 3 2 1 3 1 2 1 3 2|style="background-color:#FFF;padding:2px 30px"|

| <span style="fontbackground-sizecolor:smaller#FFF;padding:2px 30px"| <tex>код Грея для перестановки при n = 4</spantex> |style="background-color:#FFF;padding:2px 30px"| <tex>\{1 , \underline{2 , 3 4 }\}</tex> 2 1 3 4 |style="background-color:#FFF;padding:2px 30px"| берем следующую перестановку и записываем тройку в конец 2 3 1 4 |- 2 3 4 1 |style="background-color:#FFF;padding:2px 30px"| <tex>5</tex> 3 2 4 |style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{1 , 3 }, 2 1 4 \} </tex> 3 1 2 4 |style="background-color:#FFF;padding:2px 30px"| двигаем в начало 1 3 2 4 |- 1 3 4 2 |style="background-color:#FFF;padding:2px 30px"| <tex>6</tex> |style="background-color:#FFF;padding:2px 30px"| <tex>\{3 , 1 4 , 2 \} </tex> 3 4 1 2 3 4 2 1 4 3 2 1 4 3 1 2 4 1 3 2 1 4 3 2 1 4 2 3 4 1 2 3 4 2 1 3 4 2 3 1 2 4 3 1 2 4 1 3 2 1 4 3 1 2 4 3 |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> == Реализация в нерекурсивном виде. Алгоритм Джонсона-Троттера == === Идея ===Сопоставим каждому элементу перестановки отличаются только элементарной транспозицией<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>. === Пример работы алгоритма для n = 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, \textbf{2}\}\;\;\;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> === Псевдокод ===<code> <font color=darkgreen>//Элементы нумеруются начиная с 1 </font color=darkgreen> '''list<list<int>>''' gray_code(n): '''list<int>''' perm = {1, ... , n} '''list<char>''' dir = {←, ... , ←} '''list<list<int>>''' result '''while''' ''true'' result.append(perm); <font color=darkgreen> //добавляем в ответ текущую перестановку</font color=darkgreen> '''int''' id = -1; <font color=darkgreen> //индекс наибольшего подвижного элемента </font color=darkgreen> '''for''' i = 1 '''to''' n '''if''' (perm[i] - подвижный) '''and''' ((id == -1) '''or''' (perm[i] > perm[id])) id = i '''if''' (id == -1) '''break''' <font color=darkgreen> //не нашли подвижного элемента</font color=darkgreen> '''for''' i = 1 '''to''' n '''if''' (perm[i] > perm[id]) reverse(dir[i]) <font color=darkgreen> //меняем направление стрелки</font color=darkgreen> swap(id) <font color=darkgreen> //меняем элемент perm[id], dir[id] c элементом по направлению стелки</font color=darkgreen> '''return''' result </code>

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

== '''Построения Кода Грея для перестановок''' ==Будем использовать обозначения:Строим из рекурсивных соображений*<tex>\overset{\text {$\to$}}{a}</tex> {{---}} элемент с заданным направлением(компонента). При фиксированной перестановки из *<tex>P[i]</tex>k {{- 1--}} перестановка с номером <tex>i</tex> элемента можно перебрать все .*<tex>kP[i]\backslash\{a\}\;</tex> вариантов добавления к этой перестановке элемента {{---}} перестановка с номером <tex>ki</tex>, и этот перебор можно осуществить передвигая элемент без элемента <tex>ka</tex> каждый раз на соседнее место, Например.

365214'''7''' -{{Утверждение|id=approval1|statement=Число <tex> 36521'''7'''4 -n</tex> 3652'''7'''14 -в перестановке не является подвижным элементом тогда и только тогда, когда первая компонента перестановки есть <tex>\overset{\text {$\leftarrow$}}{n}</tex> или последняя компонента есть <tex>\overset{\text {$\to$}}{n}</tex> 365'''7'''214 и т. д.}}

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

''Начальное состояниеТеперь докажем основную лемму.''{{Лемма|id=lemma2|statement=Алгоритм Джонсона-Троттера строит все перестановки из <tex> r = (1, 2n</tex> элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.|proof=Доказывать будем по индукции.., k)Для <tex>n = 1\; - </tex>очевидно. Предположим, что для <tex> p = (n - 1</tex> алгоритм строит перестановки корректно. Докажем, 2, что алгоритм будет корректно строить перестановки и для <tex>n</tex> элементов..., k); Разобьём все <tex>n!</tex> перестановок на блоки по <tex>n</tex>(подряд). В силу вышедоказанной леммы в каждом блоке <tex> t P[i]\backslash\{n\} = P[i + 1]\backslash\{n\} = (0, 0, ...= P[i + n]\backslash\{n\}</tex>, 0)если <tex>i\; - </tex>начало группы. Значит, в каждой группе какая-то перестановка из <tex> d = (n -1</tex> элемента дополняется до перестановки из <tex>n</tex> всеми возможными способами. Теперь докажем, -1что на переход между блоками элемент <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>tn</tex> на 1элементов. Немного модифицируем алгоритм. При этом несколько младших разрядов получат нулевые значенияЗаметим, а что в одном из разрядов, каждом блоке нам нужно искать максимальный элемент только один раз. В остальных случаях этим элементом будет <tex>jn</tex>-м. Следовательно, значение увеличится на 1 менять направление стрелок нужно тоже только один раз(при в остальных случаях менять направления не нужно, так как <tex>j = 1n</tex> процесс заканчивается- подвижный элемент, а менять направление стрелок нужно только у бóльших элементов). Сменить направление движения всех элементов младше Следовательно, блок выполняется за <tex>jO(n) + O(n) + O(n) = O(n)</tex>-го, т.е. положить Всего блоков <tex>d_i</tex> для <tex>i > j -\:(n - 1)!</tex>. Поменять местами Общая асимптотика <tex>j</tex>-й элемент и соседний и соседний с ним O(n) \cdot (если <tex>d_j = n -1)! = O(n!)</tex> - левый, иначе - правый). {| class ===Сравнение с рекурсивным алгоритмом== "standard" border = "1"!i|t|d|p|r|j|Комментарии|Главным приемуществом алгоритма Джонсона-!||||||-!|}Элемент Троттера является то, что нам не нужно хранить все предыдущие перестановки (из <tex>j</tex> стоит на месте <tex>s = p_in - 1</tex>элемента), а только текущую. Это значитСледовательно, что этот алгоритм потребляет только <tex>r_s = jO(n)</tex>памяти. Соседнее место Также, из- это <tex>s' за нерекурсивности этот алгоритм работает быстрее. ===Интересный факт=== p_i + d_j</tex>. На нем стоит какойСуществует более общая формулировке задачи {{---то элемент <tex>j' = r_s' </tex>}} для двух соседних перестановок должно выполняться, что позиции одинаковых чисел в них отличаются не более, чем на единицу. Поменять местами в перестановке элементы Для этой формулировки верно, что для любой перестановки <tex>ju</tex> и число различных перестановок <tex>j'v</tex> означает поменять местами содержимое , которые могут стоять после <tex>p_i</tex> и <tex>p_j'u</tex>, a также равно <tex>r_s</tex> и <tex>r_s'n + 1</tex>числу Фибоначчи. Этот факт был открыт студентом нашего университета. == Сведение задачи построения кода Грея для перестановок к графам ==

== '''Сведение задачи построение кода Грея для перестановок к графам''' ==Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть [[Основные_определения_теории_графов | граф]], вешины вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам <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[[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]