Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# Get Them All. Algorithms and Permutations

DOI link for Get Them All. Algorithms and Permutations

Get Them All. Algorithms and Permutations book

# Get Them All. Algorithms and Permutations

DOI link for Get Them All. Algorithms and Permutations

Get Them All. Algorithms and Permutations book

## ABSTRACT

If we want to write a computer program to test a conjecture concerning permutations, we need to have an eﬃcient 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 eﬀort 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

deﬁne 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 deﬁned on Sn is called the lexicographic order. So for instance, 34152 < 35412 since the smallest index for which pi and qi are diﬀerent 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 suﬃces to have a method to ﬁnd 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.