3
$\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.

$\endgroup$
8
  • $\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$ Jan 19, 2017 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, 2017 at 13:45
  • $\begingroup$ Or can someone post the proof here? $\endgroup$
    – asv
    Jan 19, 2017 at 13:55
  • 1
    $\begingroup$ It is much better to work it out yourself. $\endgroup$ Jan 19, 2017 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, 2017 at 15:47

1 Answer 1

3
$\begingroup$

One can try to come up with the algorithm by oneself (thereby proving its correctness) after incremental understanding of: (a) how to define a permutation as "larger" (lexciographically) than another one, (b) what really the very next permutation of $P$ "looks like" compared to $P$ (how/where it differs from $P$). Once we find-out some properties, we may be able to write this algorithm ourselves.

Some outline:

  1. define the "lexicographic order" of permutations $P_1$ and $P_2$. Say, $k$ is the very first index at which they differ. Then the "order" of their elements at index $k$ decides the "lexicographic order" of $P_1$ and $P_2$.

  2. So what should be the smallest and largest permutation of array $a$ ?

  3. Suppose array $a$ currently holds permutation $P$. Say $P'$ is the very next permutation of $P$ in the lexicographic-order, and they first differ at index $k$. Now, use the definition in (1) and the observation in (2) to find out what is the structure of elements in $P/P'$ at index $k$ and after it. You can argue that:

  • elements in $P$ after $k$ must form a decreasing-sequence (call it $S$).
  • element in $P$ at $k$ must be smaller than the largest element of $S$, which is $a[k+1]$.
  • due to above, we must have an element $a[l]$ in $S$ which is the smallest element in $S$ larger than $a[k]$. In $P'$, this element must appear at index $k$.
  • so the remaining (after $k$) elements of $P'$ are simply $S$ with $a[l]$ removed and $a[k]$ added.
  • these remaining (after $k$) elements of $P'$, must be in increasing order (for $P'$ to be the smallest possible, but larger than $P$). The 4th step in the posted algorithm is simply obtaining this increasing order by reversing the existing decreasing-sequence $S$ (now modified via swap, but continues to remain decreasing).

For further details, refer to section "Lexicographical Order" in this article (written by me).

$\endgroup$
3
  • $\begingroup$ Hi Nitin Verma, thank you for your detailed and thorough answer! I've looked through several of your answers and I am impressed. These are a helpful contribution to the site. I wonder if I might be able to make a request. When you link to an article you have written, might you be willing to indicate that this is an article you wrote? The community sometimes gets concerned when they see a large number of posts that are pointing to the poster's own site/work, and the site has some guidelines around that: cs.stackexchange.com/help/promotion. (continued) $\endgroup$
    – D.W.
    Nov 6, 2021 at 21:39
  • $\begingroup$ I think the key aspect I'd highlight is disclosing that you wrote the article. You're doing everything else great -- you are providing useful new content, that is directly relevant to the question and answers the question that was asked, and are providing links to your own work as supplementary reading. I don't want you to stop doing that, and I don't want to discourage you from participating -- this all looks great. Thank you for listening and for contributing to the site! I hope to see more of your answers! $\endgroup$
    – D.W.
    Nov 6, 2021 at 21:41
  • $\begingroup$ many thanks for letting me know, i am adding this info in my answers. $\endgroup$ Nov 7, 2021 at 8:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.