Practical Algorithms for Generating a Random Ordering of the Elements of a Weighted Set

摘要

This paper discusses the problem of efficiently generating a random ordering of the elements of an n-element weighted set, where the elements' weights are interpreted as relative probabilities. The paper reviews the current status of this problem, which includes a purely theoretical algorithm with the optimal O(n) cost, then presents several new algorithms that are simple, practical and nearly optimal, including one with an expected cost of O(n log log n) on worst-case inputs, and another one with an expected cost of O(n) when the weights are randomly chosen from distributions that are believed to be ubiquitous in the real world. It is still an open question whether there exists a practical algorithm with O(n) expected cost on worst case inputs.