On the generation of permutations

Abstract

A new incremental algorithm for generating permutations on 1,2,..n (hereafter called "arrangements') is presented. The scheme generates arrangement k +1 by reversing a certain prefix of its predecessor and linking it to the remaining unchanged part of k. The average size of this prefix tends very rapidly to 1 as n increases, and is equal to 37/30= 1,233... in the worst-case (where n=5). The proposed algorithm uses only elementary CPU operations (namely register-shifts, additions and tests - no multiplications are made) which makes it suitable for low level language implementation and saves time. A final interesting property is the possibility of compressing the results into an array of 1!+2!+..+n! digits, instead of the nn! memory cells normally required for saving all the n! arrangements on n elements.