# Correctness proof of the algoritm to generate permutations in lexicographic order

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

I would like to know a (possible formal) proof.

• You can probably find such a proof in the new volume of The Art of Computer Programming, which is reference 48 in Wikipedia. That said, this algorithm is simple enough that the proof can be taken as an exercise. – Yuval Filmus Jan 19 '17 at 13:42
• Thank you, I don't have that book. Can I find some text of that proof for free in internet? – asv Jan 19 '17 at 13:45
• Or can someone post the proof here? – asv Jan 19 '17 at 13:55
• It is much better to work it out yourself. – Yuval Filmus Jan 19 '17 at 14:01
• Suppose a permutation $\pi$ is converted into permutation $\pi'$ by this algorithm. Why $\pi'$ is larger? Why can't there exist a permutation between $\pi$ and $\pi'$? – aaaaajack Jan 19 '17 at 15:47