130
правок
Изменения
→Доказательство корректности
|id=lemma2
|statement=Алгоритм Джонсона-Троттера строит все перестановки из <tex>n</tex> элементов, причём каждая перестановка отличаются от предыдущей транспозицией двух соседних элементов.
|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> элементов всеми возможными способами.Корректность алгоритма доказана.
}}
