|
|
 |
| |
|
|
|
A Comparative Study on the Algorithms for a Generalized Josephus Problem |
|
|
|
PP: 1451-1457 |
|
|
|
Author(s) |
|
|
|
Lei Wang,
Xiaodong Wang,
|
|
|
|
Abstract |
|
|
| The classic Josephus problem can be described as follows: There are n objects, consecutively numbered from 1 through n,
arranged in a circle. We are given a positive integer k. Beginning with a designated first object, we proceed around the circle, removing
every kth object. After each object is removed, counting continues around the circle that remains. This process continues until all n
objects have been removed. In a generalized Josephus problem, a number of lives l is introduced for the problem. Each object has l
lives. The object is removed only when it has been selected l times. In this paper we present a fast algorithm for generating the Josephus
permutation for the generalized Josephus problem. Our new algorithm can also be applied to a more general case of the generalized
Josephus problem where the lives for all objects can be different. The time and space complexities of new algorithms are O(lnlogk) and
O(n) respectively. The computational experiments demonstrate that the achieved results are not only of theoretical interest, but also that
the techniques developed may actually lead to considerably faster algorithms. |
|
|
|
|
|
|
|
