Участник:ZeRoGerc — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
Строка 54: Строка 54:
 
|id=lemma2
 
|id=lemma2
 
|statement=Алгоритм Джонсона-Троттера строит все перестановки из <tex>n</tex> элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.
 
|statement=Алгоритм Джонсона-Троттера строит все перестановки из <tex>n</tex> элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.
|proof=
+
|proof=Доказывать будем по индукции. Для <tex>n = 1</tex> - очевидно. Предположим что для <tex>n - 1</tex> алгоритм строит перестановки корректно. Докажем что алгоритм будет корректно строить перестановки и для <tex>n</tex> элементов. Разобём все <tex>n!</tex> перестановок на блоки по <tex>n</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> элементов всеми возможными способами.
 +
Корректность алгоритма доказана. 
 
}}
 
}}

Версия 19:32, 29 ноября 2014

Алгоритм Джонсона-Троттера(англ. Johnson-Trotter algorithm) - алгоритм генерации всех перестановок из [math]n[/math] элементов. Причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.

Идея

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

Пример работы алгоритма для n = 3

  • [math] p = \{1, 2, \textbf{3}\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
  • [math] p = \{1, \textbf{3}, 2\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
  • [math] p = \{3, 1, \textbf{2}\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
  • [math] p = \{\textbf{3}, 2, 1\}\;\;\;d = \{[/math]→, ←, ←[math]\}[/math]
  • [math] p = \{2, \textbf{3}, 1\}\;\;\;d = \{[/math]←, →, ←[math]\}[/math]
  • [math] p = \{2, 1, 3\}\;\;\;d = \{[/math]←, ←, →[math]\}[/math]

Псевдокод

 //Элементы нумеруются начиная с 1  
p = {1, ... , n}
d = {←, ... , ←}
while (true){
  print(); // печатаем текущую перестановку
  id = -1; // индекс наибольшего подвижного элемента 
  for i (1 .. n){
     if (p[i] - подвижный) and ((id = -1) or (p[i] > p[id]))
       id = i
  }
  if (id = -1) break // не нашли подвижного элемента
  swap(id) //меняем элемент p[id], d[id] c элементом по направлению стелки 
}

Доказательство корректности

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

Будем использовать обозначения:

  • [math](a,[/math][math])[/math] - элемент с заданным направлением(компонента).
  • [math]P[i][/math] - перестановка с номером [math]i[/math].
  • [math]P[i]\backslash\{a\}[/math] - перестановка с номером [math]i[/math] без элемента [math]a[/math].
Утверждение:
Число [math]n[/math] в перестановке не является подвижным элементом тогда и толко тогда когда первая компонента перестановки есть [math](n,[/math][math])[/math] или последняя компонента есть [math](n,[/math][math])[/math].


Лемма:
Если в перестановке [math]P[i][/math] есть подвижный элемент [math]a \neq n[/math] то также определены перестановки [math]P[i + 1] ... P[i + n][/math] причём [math]P[i + 1]\backslash\{n\} = P[i + 2]\backslash\{n\} = ... = P[i + n]\backslash\{n\}[/math].
Доказательство:
[math]\triangleright[/math]
Заметим, что если в перестановке есть подвижный элемент [math]a \neq n[/math], то после транспозиции его с соседним элемнтом(по направлению стрелки), нам нужно будет заменить направление стрелок у всех элементов больше [math]a[/math]. Так как [math]n[/math] больше любого элемента из перестановки, то направление стрелеки у него тоже изменится. По нашему утверждению либо в новой перестановке окажется компонента [math](n,[/math][math])[/math] на первой позиции, либо компонента [math](n,[/math][math])[/math] на последней позиции. В обоих случаях [math]n[/math] окажется подвижным элементом в следующих [math]n[/math] перестановках. Так как в следующих [math]n[/math] перестановках подвижным элементом будет только [math]n[/math], то [math]P[i + 1]\backslash\{n\} = P[i + 2]\backslash\{n\} = ... = P[i + n]\backslash\{n\}[/math].
[math]\triangleleft[/math]

Теперь докажем основную лемму.

Лемма:
Алгоритм Джонсона-Троттера строит все перестановки из [math]n[/math] элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.
Доказательство:
[math]\triangleright[/math]

Доказывать будем по индукции. Для [math]n = 1[/math] - очевидно. Предположим что для [math]n - 1[/math] алгоритм строит перестановки корректно. Докажем что алгоритм будет корректно строить перестановки и для [math]n[/math] элементов. Разобём все [math]n![/math] перестановок на блоки по [math]n[/math](Подряд). В силу вышедоказанной леммы в каждой группе P[i]\backslash\{n\} = P[i + 1]\backslash\{n\} = ... = P[i + n]\backslash\{n\}</tex>, если [math]i[/math] - начало группы. Значит в каждой группе какая-то перестановка из [math]n - 1[/math] элементов дополняется до перестановки из [math]n[/math] всеми возможными способами. Теперь докажем, что на переход между блоками [math]n[/math] никак не влияет. Заметим, что при переходе между блоками [math]n[/math] является неподвижным элементом. В силу нашего утверждения [math]n[/math] стоит либо на первой, либо на последней позиции. Так как [math]n[/math] больше любого элементаб, то никакой подвижный элемент не может указывать на [math]n[/math]. В силу этих фактов [math]n[/math] никак не повлияет на переход между блоками. Из этого можно сделать вывод, что при переходе между блоками перестановки строяться так же, как и для перестановки из [math]n - 1[/math] элемента, а каждая такая перестановка дополняется до перестановки из [math]n[/math] элементов всеми возможными способами.

Корректность алгоритма доказана.
[math]\triangleleft[/math]