
110 Combinatorics of Permutations, Second Edition
Thus the second cycle of p must start with the leftmost entry q
j
of q that
is larger than q
1
. By identical argument, the third cycle of q must start with
the leftmost entry of q larger than q
j
, and so on. The procedure will stop
with the cycle that starts with the entry n. This yields a deterministic, and
always executable, algorithm to find the unique preimage of q under p.
In our running example, we have q = 2417635. This yields q
1
=2. The
smallest j so that q
j
>q
1
is j = 2, so the second cycle will start in the second
position. Then, the leftmost entry larger than 4 is 7, so the third cycle starts
with ...