2017年1月
Linear-time generation of uniform random derangements encoded in cycle notation
Discrete Applied Mathematics
- ,
- 巻
- 217
- 号
- 開始ページ
- 722
- 終了ページ
- 728
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.dam.2016.10.001
- 出版者・発行元
- Elsevier Science BV
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(log n!) = O(n log n) bits can be executed in constant time. (C) 2016 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.dam.2016.10.001
- ISSN : 0166-218X
- eISSN : 1872-6771
- Web of Science ID : WOS:000390510600030