Generating Permutations Lexicographically: Next in Lexicographical Order

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Next in Lexicographical Order

Suppose, in our program we are generating permutations in array a itself, and at certain point have generated some permutation P in it:

P = (a0,a1,a2,...,aN− 1)

What is the permutation P′ which is the very next permutation of P in the lexicographic ordering? That is, among all permutations larger than P, P′ is the smallest.

Say, the ﬁrst element at which P and P′ diﬀer is their m^th element. Call the m^th element in P′ as b. So, a_m−1≠b and since P < P′, a_m−1 < b.

Note that, among all permutations having their ﬁrst m elements’ sequence same as P, P must be the largest. Because, if P is not the largest, then there is a permutation Q larger than P sharing ﬁrst m elements’ sequence with it. That is, P < Q. The initial m elements of Q being same as of P (till a_m−1) implies Q < P′. So, P < Q < P′. That is a contradiction, since P′ is the very next permutation after P.

Since P is the largest among all permutations having their ﬁrst m elements’ sequence same as P, we can conclude this about the remaining N −m elements of P:

am > am+1 > am+2 > ...> aN−1

(1)

Since P′ shares its ﬁrst m− 1 elements with P, and its m^th element b diﬀers from a_m−1, we can say that b is one of the remaining N − m elements of P, referred as set S:

S = {am, am+1,am+2, ...,aN− 1}

Note that elements of S can be ordered as in (1). Since P′ is the smallest of all permutations larger than P, b has to be the smallest of the elements in set S such that b > a_m−1. Say, b = a_k. Since a_m is the largest in set S, such b exists only if:

am −1 < am

(2)

The elements in P′ after its m^th element b are actually this set of N − m elements: S′ = (S ∖{a_k}) ∪{a_m−1}.

Again, since P′ is the smallest of all permutations larger than P, all N − m elements in P′ after b must be in increasing order. That is, elements of set S′ in increasing order.

We already know the order of elements of set S from ordering (1). That ordering can be modiﬁed by removing a_k and adding a_m−1. Since a_k is the smallest element in set S which is larger than a_m−1, so, in that ordering, a_k can be removed and a_m−1 added at the same position, while maintaining the decreasing order. This modiﬁcation in (1) gives us a decreasing order of elements of set S′, which can be reversed to obtain increasing order.

[Prev] [Up] [Next]