Combinatorics of Permutations, 3rd Edition

8Get Them All. Algorithms and Permutations.

DOI: 10.1201/9780429274107-8

8.1 Generating Permutations

8.1.1 Generating All n-Permutations

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=p_1{p}_2\cdots p_n<q_1{q}_2\cdots q_n$ if for the smallest index i for which $p_i\ne q_i$, we have $p_i<q_i$. The total order defined on ...