Generation of permutations by transposition

Abstract

Many problems require the generation of all n factoral permutations of n marks (called arrangements). A generation scheme is presented whereby each step consists of merely transposing two of the marks. The bookkeeping is quite simple, thus this scheme is somewhat faster than either the usual dictionary order method or the Tompkins-Paige method. The important property of leaving the (j+1)st position alone until all j factoral arrangements of the marks in the first j positions have been generated is preserved. (auth)