130
правок
Изменения
→Доказательство корректности
== Доказательство корректности ==
Очевидно что требование о том что каждая генерируемая перестановка отличается от предыдущей транспозицией двух соседних элементов выполнено исходя из самого алгоритма. Осталось доказать , что таким образом мы сгенерируем все перестановки. Будем использовать обозначениe <tex>(a,</tex> ←<tex>)</tex> - элемент с заданным направлением(компонента).
{{Утверждение
|id=id1
|statement=Число <tex>n</tex> в перестановке не является подвижным элементом тогда и толко тогда когда первая компонента перестановки есть <tex>(n,</tex> ←<tex>)</tex> или последняя компонента есть <tex>(n,</tex> →<tex>)</tex>
}}
