More on permutation generation methods

We study a class of recursive permutation generation methods which construct a sequence of alln! permutations ofn elements by repeatedly generating all permutations of the elements in the firstn?1 positions and exchanging one of them with the element in then-th position. We give a general principle which enables us to obtain a whole class of permutation generation methods. This class includes the well-known algorithms of Wells and Heap as special cases, but contains also many new simple algorithms. Moreover, we are able to produce permutation generation methods with prescribed properties concerning the change that should be made in order to skip a block ofm! permutations with fixed elements in positionsm+1, …,n. For any method in our class, this change is a single transposition for any oddm>1, and a cyclic shift along a cycle of lengthm for any evenm.