If we want to write a computer program to test a conjecture concerning permutations, we need to have an efficient method to generate all n-permutations for our machine. If the conjecture only concerns permutations with some restrictions, we can save a lot of time and effort by having a fast way to generate only those permutations with the required property. One can certainly list all permutations lexicographically. That is, let us

define a partial order on the set of all n-permutations as follows. Let p = p1p2 · · · pn < q1q2 · · · qn if for the smallest index i for which pi = qi, we have pi < qi. The total order defined on Sn is called the lexicographic order. So for instance, 34152 < 35412 since the smallest index for which pi and qi are different is i = 2, and p2 < q2. It is obvious that the smallest element of Sn in the lexicographic order is the

identity permutation 12 · · ·n. Therefore, in order to construct an algorithm to list all n-permutations in the lexicographical order, it suffices to have a method to find the permutation immediately following a given permutation p in the lexicographic order. Such a method is provided by the following proposition. Recall that in a poset we say that q covers p if p < q, and there is no r so that p < r < q.