130
правок
Изменения
→Доказательство корректности
== Доказательство корректности ==
Очевидно что требование о том что каждая генерируемая перестановка отличается от предыдущей транспозицией двух соседних элементов выполнено исходя из самого алгоритма. Осталось доказать что таким образом мы сгенерируем все перестановки. Будем использовать обозначениe ''(a, ←)'' - элемент с заданным направлением(компонента).
Число n в перестановке не является подвижным элементом тогда и толко тогда когда первая компонента перестановки есть (n, ←) или последняя компонента есть (n, →)
