2
$\begingroup$

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].

(from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

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

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 19 '17 at 13:42
  • $\begingroup$ Thank you, I don't have that book. Can I find some text of that proof for free in internet? $\endgroup$ – asv Jan 19 '17 at 13:45
  • $\begingroup$ Or can someone post the proof here? $\endgroup$ – asv Jan 19 '17 at 13:55
  • 1
    $\begingroup$ It is much better to work it out yourself. $\endgroup$ – Yuval Filmus Jan 19 '17 at 14:01
  • 2
    $\begingroup$ 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'$? $\endgroup$ – aaaaajack Jan 19 '17 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.