کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949777 | 1364256 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear-time generation of uniform random derangements encoded in cycle notation
ترجمه فارسی عنوان
تولید زمان خطی از اختلالات تصادفی یکنواخت کدگذاری شده در علامت چرخه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل ترکیبی الگوریتم، نسل تصادفی، خط زمان خرابکاری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 3, 30 January 2017, Pages 722-728
Journal: Discrete Applied Mathematics - Volume 217, Part 3, 30 January 2017, Pages 722-728
نویسندگان
Kenji Mikawa, Ken Tanaka,