Редактирование: Коды Грея для перестановок

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
'''Коды Грея для перестановок'''(англ. ''Gray code for permutation'') {{---}} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Элементарная транспозиция''' (англ. ''Adjacent transposition'') {{---}} перестановка местами двух соседних элементов.
+
'''Элементарная транспозиция'''(англ. Adjacent transposition) перестановка местами двух соседних элементов.
 
}}  
 
}}  
'''Коды Грея для перестановок''' (англ. ''Gray code for permutation'') {{---}} упорядочение перестановок, при котором соседние перестановки отличаются только элементарной транспозицией.
 
 
== Построение кода Грея для перестановок ==
 
== Построение кода Грея для перестановок ==
  
Строка 33: Строка 33:
  
 
Таким образом получаем для каждой перестановки длиной <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>, причём соседние отличаются в одной элементарной транспозиции.
 
Таким образом получаем для каждой перестановки длиной <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>, причём соседние отличаются в одной элементарной транспозиции.
 +
 +
== Пример применения алгоритма ==
 +
 +
Рассмотрим код Грея для длины <tex>n = 2</tex>:
 +
 +
* <tex>\{2, 1\}</tex>
 +
* <tex>\{1, 2\}</tex>
 +
 +
Тогда следуя алгоритму полученный код будет выглядеть так (подчёркнуты пары переставляемых элементов):
 +
 +
* <tex>\{\underline{3, 2}, 1\}</tex> {{---}} берем первую перестановку и добавляем в начало тройку
 +
* <tex>\{2, \underline{3, 1}\}</tex> {{---}} двигаем до последней позиции
 +
* <tex>\{\underline{2, 1}, 3\}</tex>
 +
* <tex>\{1, \underline{2, 3}\}</tex> {{---}} берем следующую перестановку и записываем тройку в конец
 +
* <tex>\{\underline{1, 3}, 2\}</tex> {{---}} двигаем в начало
 +
* <tex>\{3, 1, 2\}</tex>
 +
 +
Код Грея получен.
 +
 +
== Псевдокод получения кода Грея ==
 +
 +
Получаем код Грея рекурсивно, в базовом случае <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>
  
 
== Примеры кодов Грея для перестановок ==
 
== Примеры кодов Грея для перестановок ==
 +
 
'''Перестановки для n = 2'''
 
'''Перестановки для n = 2'''
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 47: Строка 93:
 
|}
 
|}
  
'''Перестановки для n = 3''' (подчёркнуты пары переставляемых элементов)
+
'''Перестановки для n = 3'''
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| Номер
 
!style="background-color:#EEE"| Номер
 
!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>1</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{3, 2}, 1\} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{3, 1, 2\} </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</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{2, \underline{3, 1}\} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, 3, 2\} </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>3</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{2, 1}, 3\}</tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, 2, 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>4</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{1, \underline{2, 3}\}</tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{2, 1, 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>5</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\underline{1, 3}, 2\} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{2, 3, 1\} </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>6</tex>
|style="background-color:#FFF;padding:2px 30px"| <tex>\{3, 1, 2\} </tex>
+
|style="background-color:#FFF;padding:2px 30px"| <tex>\{3, 2, 1\} </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>.
+
Сопоставим каждому элементу перестановки <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 ===
 
=== Пример работы алгоритма для n = 3 ===
Строка 157: Строка 169:
 
|id=lemma1  
 
|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>.
 
|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>.
+
|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>.
 
}}
 
}}
  
Строка 173: Строка 185:
  
 
===Сравнение с рекурсивным алгоритмом===
 
===Сравнение с рекурсивным алгоритмом===
Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из <tex>n - 1</tex> элемента), а только текущую. Следовательно, этот алгоритм потребляет только <tex>O(n)</tex> памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее.
+
Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из <tex>n - 1</tex> элемента), а только текущую. Следовательно, этот алгоритм потребляет только <tex>O(n)</tex> памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее. Это можно строго доказать, но доказательство довольно громозодкое и приводить его мы здесь не будем.
 
 
===Интересный факт===
 
Существует более общая формулировке задачи {{---}} для двух соседних перестановок должно выполняться, что позиции одинаковых чисел в них отличаются не более, чем на единицу.
 
Для этой формулировки верно, что для любой перестановки <tex>u</tex> число различных перестановок <tex>v</tex>, которые могут стоять после <tex>u</tex>, равно <tex>n + 1</tex> числу Фибоначчи.
 
Этот факт был открыт студентом нашего университета.
 
  
 
== Сведение задачи построения кода Грея для перестановок к графам ==
 
== Сведение задачи построения кода Грея для перестановок к графам ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)