Abstract
A new algorithm for generating derangements based on a well known permutation generation method is presented and analysed. The algorithm is shown to be superior in storage and time requirements to the existing method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. G. Akl,An Algorithm for generating derangements, Technical Report No. 78-71, DOCIS, Queen's University, Kingston, Ontario, Canada.
J. R. Bitner, G. Ehrlich and E. M. Reingold,Efficient generation of the binary reflected Gray code and its applications, CACM, Vol. 19, No. 9 (1976), 517–521.
G. Ehrlich,Loopless algorithms for generating permutations, combinations and other combinatorial configurations, JACM, Vol. 20, No. 3 (1973), 500–513.
S. Even,Algorithmic Combinatorics, Macmillan, New York, 1973, pp. 55–56.
E. M. Reingold, J. Nievergelt and N. Deo,Combinatorial Algorithms, Solutions Manual, Prentice-Hall, Englewood Cliffs, New Jersey, 1978, pp. 111–119.
J. Riordan,An Introduction to Combinatorial Analysis, John Wiley, New York, 1958, p. 188.
R. Sedgewick,Permutation generation methods, Computing Surveys, Vol. 9, No. 2 (1977), 137–164.
S. Zacks, and D. Richards,Generating trees and other combinatorial objects lexicographically, SIAM J. Comput., Vol. 8, No. 1 (1979), 73–81.
Author information
Authors and Affiliations
Additional information
This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC-A3336.
Rights and permissions
About this article
Cite this article
Akl, S.G. A new algorithm for generating derangements. BIT 20, 2–7 (1980). https://doi.org/10.1007/BF01933579
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF01933579