Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949777 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
We present a linear-time algorithm for generating random derangements. Several algorithms for generating random derangements have recently been published. They are enhancements of the well-known Fisher-Yates shuffle for random permutations, and use the rejection method. The algorithms sequentially generate random permutations, and therefore pick only derangements by omitting the other permutations. A probabilistic analysis has shown that these algorithms could be run in an amortized linear-time. Our algorithm is the first to achieve an exact linear-time generation of random derangements. We use a computational model such that arithmetic operations and random access for O(logn!)=O(nlogn) bits can be executed in constant time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kenji Mikawa, Ken Tanaka,