Lexicographic Ordering

Overview

A lexicographic ordering of English words is the ordering of the words as found within a dictionary.

Iteration

We can find the next lexicographic ordering of an array via a procedure of "pivot", "swap", and "reverse".

[ a₁ a₂ ... aᵢ | aᵢ₊₁ aᵢ₊₂ ... aₙ ]

Here the RHS side is the longest increasing sequence we could find, from right to left. That is, $a_{i+1}>a_{i+2}>\cdots >a_n$. Denote $a_i$ as the pivot. Next, swap the smallest element in the RHS greater than $a_i$, say $a_j$, with $a_i$. This produces

[ a₁ a₂ ... aⱼ | aᵢ₊₁ aᵢ₊₂ ... aᵢ ... aₙ ]

Notice the RHS remains in sorted order. Since $a_j$ was the next smallest element, reversing the reverse-sorted RHS produces the next permutation, lexicographically speaking:

[ a₁ a₂ ... aⱼ | aₙ ... aᵢ ... aᵢ₊₂ aᵢ₊₁ ]

Eventually the swapped $a_j$ will be the largest in the RHS ensuring that the breakpoint will eventually move one more position leftward.