Коды Грея для перестановок — различия между версиями
Niko (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 126 промежуточных версий 10 участников) | |||
Строка 1: | Строка 1: | ||
− | {| | + | {{Определение |
− | + | |definition = | |
− | + | '''Элементарная транспозиция''' (англ. ''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> | ||
− | |||
− | |||
− | |||
− | + | Таким образом получаем для каждой перестановки длиной <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="background-color:#FFF;padding:2px 30px"| <tex>1</tex> | |
− | + | |style="background-color:#FFF;padding:2px 30px"| <tex>\{2, 1\} </tex> | |
− | |||
− | | - | ||
− | | | ||
− | |||
− | | - | ||
− | | | ||
|- | |- | ||
+ | |style="background-color:#FFF;padding:2px 30px"| <tex>2</tex> | ||
+ | |style="background-color:#FFF;padding:2px 30px"| <tex>\{1, 2\} </tex> | ||
+ | |} | ||
− | + | '''Перестановки для 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"| | |
− | | - | ||
− | | | ||
− | | | ||
− | | 3 | ||
− | | | ||
|- | |- | ||
− | + | |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"| | ||
+ | |} | ||
− | + | == Псевдокод получения кода Грея == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Получаем код Грея рекурсивно, в базовом случае <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> {{---}} перестановка с номером <tex>i</tex>. | |
− | + | *<tex>P[i]\backslash\{a\}\;</tex> {{---}} перестановка с номером <tex>i</tex> без элемента <tex>a</tex>. | |
− | |||
− | |||
− | |||
− | |||
− | + | {{Утверждение | |
− | | | + | |id=approval1 |
− | | | + | |statement=Число <tex>n</tex> в перестановке не является подвижным элементом тогда и только тогда, когда первая компонента перестановки есть <tex>\overset{\text {$\leftarrow$}}{n}</tex> или последняя компонента есть <tex>\overset{\text {$\to$}}{n}</tex>. |
− | + | }} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | {{Лемма | |
− | | | + | |id=lemma1 |
− | | | + | |statement=Если в перестановке <tex>P[i]</tex> есть подвижный элемент <tex>a \neq n</tex>, то также определены перестановки <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=Заметим, что если в перестановке есть подвижный элемент <tex>a \neq n</tex>, то после транспозиции его с соседним элементом(по направлению стрелки), нам нужно будет заменить направление стрелок у всех элементов больше <tex>a</tex>. Так как <tex>n</tex> больше любого элемента из перестановки, то направление стрелки у него тоже изменится. По нашему утверждению, либо в новой перестановке окажется компонента <tex>\overset{\text {$\to$}}{n}</tex> на первой позиции, либо компонента <tex>\overset{\text {$\leftarrow$}}{n}</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>. |
− | + | }} | |
− | |||
− | |||
− | |||
− | + | Теперь докажем основную лемму. | |
− | | | + | {{Лемма |
− | | --++ | + | |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> элемента), а только текущую. Следовательно, этот алгоритм потребляет только <tex>O(n)</tex> памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ===Интересный факт=== | |
− | + | Существует более общая формулировке задачи {{---}} для двух соседних перестановок должно выполняться, что позиции одинаковых чисел в них отличаются не более, чем на единицу. | |
− | + | Для этой формулировки верно, что для любой перестановки <tex>u</tex> число различных перестановок <tex>v</tex>, которые могут стоять после <tex>u</tex>, равно <tex>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 | ||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | |||
+ | [[Категория: Комбинаторика ]] |
Текущая версия на 19:28, 4 сентября 2022
Определение: |
Элементарная транспозиция (англ. Adjacent transposition) — перестановка местами двух соседних элементов. |
Коды Грея для перестановок (англ. Gray code for permutation) — упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.
Построение кода Грея для перестановок
Будем строить код Грея для длины код Грея для перестановок длиной . Возьмем первую перестановку из известного нам кода. Она имеет следующий вид:
. Предположим, что нам известенСначала запишем число
в начало этой перестановки, после чего будем двигать его вправо элементарными транспозициями (подчёркнуты пары переставляемых элементов).Получим
различных перестановок, отличающихся одной элементарной транспозицией. Возьмем следующую перестановку из кода Грея для перестановок длины и припишем в конце число . Эта перестановка отличается на одну элементарную транспозицию (последние элементы совпадают, а префиксы длины отличаются на элементарную транспозицию). Пусть она имеет следующий вид:
Элемент
записываем в конец и начинаем "двигать" его влево:Продолжаем аналогично. Для каждой перестановки дописываем
в один конец (поочерёдно), и с помощью элементарных транспозиций двигаем в другой конец, при этом добавляя каждую промежуточную перестановку в список.Таким образом получаем для каждой перестановки длиной
(всего штук) по новых перестановок, в сумме перестановок. Все они различны, так как для любых двух перестановок из нового кода Грея элемент стоит на разных позициях,а если стоит на одной и той же позиции, то эти перестановки образованы от разных перестановок длиной . Так же все соседние перестановки отличаются ровно в одной элементарной транспозиции. Итого, мы получили список из различных перестановок длиной , причём соседние отличаются в одной элементарной транспозиции.Примеры кодов Грея для перестановок
Перестановки для n = 2
Номер | Перестановка |
---|---|
Перестановки для n = 3 (подчёркнуты пары переставляемых элементов)
Номер | Перестановка | Пояснение |
---|---|---|
берем первую перестановку и добавляем в начало тройку | ||
двигаем до последней позиции | ||
берем следующую перестановку и записываем тройку в конец | ||
двигаем в начало | ||
Псевдокод получения кода Грея
Получаем код Грея рекурсивно, в базовом случае
возвращаем список из одной перестановки .list<list<int>> gray_code(n): if n == 1 return [{1}] //возращаем список из одной перестановки else list<list<int>> result = [] //пустой список list<list<int>> perms = gray_code(n - 1) //perms — перестановки из n - 1 элемента bool backward = false //переменная которая говорит с какой стороны заполнять перестановку for perm in perms //perm — текущая перестановка if backward list<int> current = concat(perm, {n}) //дописываем {n} в конец perm result.append(current) //добавляем в ответ перестановку current for i = n downto 2 swap(current[i - 1], current[i]) //переставляем n result.append(current) //добавляем в ответ перестановку current else list<int> current = concat({n}, perm) //дописываем {n} в начало perm result.append(current) //добавляем в ответ перестановку current for i = 1 to n - 1 swap(current[i], current[i + 1]) //переставляем n result.append(current) //добавляем в ответ перестановку current backward = not backward //меняем состояние backward return result //возвращаем ответ в виде списка
Реализация в нерекурсивном виде. Алгоритм Джонсона-Троттера
Идея
Сопоставим каждому элементу перестановки
направление . Будем указывать направление при помощи стрелок ← ("влево") или →("вправо"). Назовём элемент подвижным, если по направлению стрелки стоит элемент меньше его. Например, для , подвижными являются элементы и . На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. Изначально .Пример работы алгоритма для n = 3
Псевдокод
//Элементы нумеруются начиная с 1 list<list<int>> gray_code(n): list<int> perm = {1, ... , n} list<char> dir = {←, ... , ←} list<list<int>> result while true result.append(perm); //добавляем в ответ текущую перестановку int id = -1; //индекс наибольшего подвижного элемента for i = 1 to n if (perm[i] - подвижный) and ((id == -1) or (perm[i] > perm[id])) id = i if (id == -1) break //не нашли подвижного элемента for i = 1 to n if (perm[i] > perm[id]) reverse(dir[i]) //меняем направление стрелки swap(id) //меняем элемент perm[id], dir[id] c элементом по направлению стелки return result
Доказательство корректности
Очевидно, что требование о том, что каждая генерируемая перестановка отличается от предыдущей транспозицией двух соседних элементов выполнено исходя из самого алгоритма. Осталось доказать, что таким образом мы сгенерируем все перестановки.
Будем использовать обозначения:
- — элемент с заданным направлением(компонента).
- — перестановка с номером .
- — перестановка с номером без элемента .
Утверждение: |
Число в перестановке не является подвижным элементом тогда и только тогда, когда первая компонента перестановки есть или последняя компонента есть . |
Лемма: |
Если в перестановке есть подвижный элемент , то также определены перестановки . Причём, . |
Доказательство: |
Заметим, что если в перестановке есть подвижный элемент | , то после транспозиции его с соседним элементом(по направлению стрелки), нам нужно будет заменить направление стрелок у всех элементов больше . Так как больше любого элемента из перестановки, то направление стрелки у него тоже изменится. По нашему утверждению, либо в новой перестановке окажется компонента на первой позиции, либо компонента на последней позиции. В обоих случаях окажется подвижным элементом в следующих перестановках. Так как в следующих перестановках подвижным элементом будет только , то .
Теперь докажем основную лемму.
Лемма: |
Алгоритм Джонсона-Троттера строит все перестановки из элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов. |
Доказательство: |
Доказывать будем по индукции. Для Корректность алгоритма доказана. очевидно. Предположим, что для алгоритм строит перестановки корректно. Докажем, что алгоритм будет корректно строить перестановки и для элементов. Разобьём все перестановок на блоки по (подряд). В силу вышедоказанной леммы в каждом блоке , если начало группы. Значит, в каждой группе какая-то перестановка из элемента дополняется до перестановки из всеми возможными способами. Теперь докажем, что на переход между блоками элемент никак не влияет. Заметим, что при переходе между блоками является неподвижным элементом. В силу нашего утверждения стоит либо на первой, либо на последней позиции. Так как больше любого элемента, то никакой подвижный элемент не может указывать на . В силу этих фактов никак не повлияет на переход между блоками. Из этого можно сделать вывод, что при переходе между блоками перестановки строятся так же, как и перестановки из элемента, а каждая такая перестановка дополняется до перестановки из элементов всеми возможными способами. |
Асимптотика
Поговорим об асиптотике. Снова разобьём наши перестановки на блоки по
элементов. Немного модифицируем алгоритм. Заметим, что в каждом блоке нам нужно искать максимальный элемент только один раз. В остальных случаях этим элементом будет . Следовательно, менять направление стрелок нужно тоже только один раз(в остальных случаях менять направления не нужно, так как - подвижный элемент, а менять направление стрелок нужно только у бóльших элементов). Следовательно, блок выполняется за . Всего блоков . Общая асимптотика .Сравнение с рекурсивным алгоритмом
Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из
элемента), а только текущую. Следовательно, этот алгоритм потребляет только памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее.Интересный факт
Существует более общая формулировке задачи — для двух соседних перестановок должно выполняться, что позиции одинаковых чисел в них отличаются не более, чем на единицу. Для этой формулировки верно, что для любой перестановки
число различных перестановок , которые могут стоять после , равно числу Фибоначчи. Этот факт был открыт студентом нашего университета.Сведение задачи построения кода Грея для перестановок к графам
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам и , соединены ребром, если образуется из однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.
См. также
Источники информации
- Романовский И.В. Дискретный Анализ - Санкт-Петербург, 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