| Presentation | 2012-11-02 Linear time generation of random derangements Kenji MIKAWA, Ken TANAKA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We present a linear time algorithm for generating random derangements. Several algorithms published in recent papers enhanced the well-known Fisher-Yates shuffle for random permutations to suit this problem with using the rejection method so that the algorithms generated random permutations sequentially and picked up only derangements by omitting the other permutations. The algorithms were ensured to run in an amortized linear time in probabilistic analysis. Our algorithm achieves an exact linear time generation of random derangements. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | combinatorial problem / algorithm / random generation / linear time / derangement |
| Paper # | CAS2012-59,MSS2012-39 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2012/10/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Linear time generation of random derangements |
| Sub Title (in English) | |
| Keyword(1) | combinatorial problem |
| Keyword(2) | algorithm |
| Keyword(3) | random generation |
| Keyword(4) | linear time |
| Keyword(5) | derangement |
| 1st Author's Name | Kenji MIKAWA |
| 1st Author's Affiliation | Center for Academic Information Service, Niigata University() |
| 2nd Author's Name | Ken TANAKA |
| 2nd Author's Affiliation | Faculty of Science, Kanagawa University |
| Date | 2012-11-02 |
| Paper # | CAS2012-59,MSS2012-39 |
| Volume (vol) | vol.112 |
| Number (no) | 274 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |