Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal
               
 
 
 
 
 
 
 
 
 
 
 
 

Content
 

Volumes > Volume 07 > No. 4

 
   

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.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved