Изменения

|proof=Доказывать будем по индукции. Для <tex>n = 1- </tex> - очевидно. Предположим что для <tex>n - 1</tex> алгоритм строит перестановки корректно. Докажем что алгоритм будет корректно строить перестановки и для <tex>n</tex> элементов. Разобём все <tex>n!</tex> перестановок на блоки по <tex>n</tex>(Подряд). В силу вышедоказанной леммы в каждом блоке <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> никак не повлияет на переход между блоками.