Permutation Enumeration: Four New Permutation Algorithms

Classical permutation enumeration algorithms encounter
special cases requiring additional computation 
every nth permutation when generating the n! permutations
on n marks.  Four new algorithms have the attribute 
that special cases occur every n(n-1)permutations. 
Two of the algorithms produce the next permutation 
with a single exchange of two marks.  The other two algorithms
infrequently exchange more than two marks, 
but the rules for generating the next permutation are
very simple.  Performance tests which have counted 
execution of assignment statements, comparisons, arithmetic
operations, and subscripted array references 
have shown superiority of the new algorithms compared to
Boothroyd's implementation of M. B. Well's algorithm 
and Ehrlich's implementation of the Johnson-Trotter algorithm.

CACM February, 1976

Ives, F. M.

permutations, loop-free algorithms

5.30

CA760203 JB January 5, 1978  9:33 AM

2834	4	2884
2884	4	2884
3115	4	2884
2417	5	2884
2884	5	2884
2884	5	2884
2884	5	2884
2908	5	2884
3115	5	2884
907	6	2884
2045	6	2884
2417	6	2884
2466	6	2884
2505	6	2884
2884	6	2884
2884	6	2884
521	6	2884
579	6	2884
785	6	2884