Reversing is Not Inherent in Lexicographical Permutation Generation

Abstract

In his comprehensive 1977 survey of permutation generation methods, Sedgewick [4] stated that "(reversing) seems to be inherent in lexicographical (permutation) generation". It is the purpose of this paper to give an algorithm which does not use reversing and to show its relationship to the classical reversing algorithm of Ord-Smith [3]. We also give a number of related algorithms to illustrate the flexibility of the new algorithm.