An O(n log m) algorithm for the Josephus Problem |
| |
Authors: | Errol L Lloyd |
| |
Affiliation: | Department of Computer Science, University of Pittsburgh, Pittsburgh, Pennsylvania 15260 USA |
| |
Abstract: | The Josephus Problem can be described as follows: There are n objects arranged in a circle. Beginning with the first object, we move around the circle and remove every m th object. As each object is removed, the circle closes in. Eventually, all n objects will have been removed from the circle. The order in which the objects are removed induces a permutation on the integers 1 through n. Knuth has described two O(n log n) algorithms for generating this permuation. The problem of determining a more efficient algorithm for generating the permutation is left open. In this paper we give an O(n log m) algorithm. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|