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