AN ANALYSIS OF A SIMPLE ALGORITHM FOR RANDOM DERANGEMENTS

AN ANALYSIS OF A SIMPLE ALGORITHM FOR RANDOM DERANGEMENTS
复制标题

一种简单的随机排列算法分析

DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Verri
M. Verri
中科院分区：
--
文献类型：
--
作者：
D. Merlini;R. Sprugnoli;M. Verri

文献摘要

被引文献

相似文献

我们考虑随机排列的均匀生成，即，没有任何固定点的排列。通过使用拒绝算法，我们改进了直接生成随机排列的方法，直到得到一个乱序。这和我们的程序都是线性的调用随机发生器的数量，但我们得到了超过36%的改善。通过使用概率生成函数，我们进行了精确的平均分析的算法，表明我们的方法是相当普遍的，可以用来分析基于相同的拒绝技术的随机生成过程。此外，重点给出了组合和和一个已知的无限下三角形阵列的一个新的解释。
We consider the uniform generation of random derangements, i.e., permutations without any fixed point. By using a rejection algorithm, we improve the straight-forward method of generating a random permutation until a derangement is obtained. This and our procedure are both linear with respect to the number of calls to the random generator, but we obtain an improvement of more than 36%. By using probability generating functions we perform an exact average analysis of the algorithm, showing that our approach is rather general and can be used to analyze random generation procedures based on the same rejection technique. Moreover, emphasis is given to combinatorial sums and a new interpretation of a known infinite lower triangular array is found.