Simulation - Data Structures and Problem Solving Using Java - page 509

First, we write a program that simulates, pass for pass, a game for any val-
ues of N and M . The running time of the simulation is O ( MN ) , which is
acceptable if the number of passes is small. Each step takes O ( M ) time
because it performs M passes. We then show how to implement each step in
O (log N ) time, regardless of the number of passes performed. The running
time of the simulation becomes O ( N log N ).

13.1.1 the simple solution

The passing stage in the Josephus problem suggests that we represent the
players in a linked list. We create a linked list in which the elements 1, 2, ,
N are inserted in order. We then set an iterator to the front element. Each pass
of the potato corresponds to a next operation on the iterator. At the last player
(currently remaining) in the list we implement the pass by creating a new iter-
ator positioned prior to the first element. This action mimics the circle. When
we have finished passing, we remove the element on which the iterator has
landed.
An implementation is shown in Figure 13.2. The linked list and iterator
are declared at lines 8 and 15, respectively. We construct the initial list by
using the loop at lines 11 and 12.
In Figure 13.2, the code at lines 18 to 25 plays one step of the algorithm
by passing the potato (lines 18 to 24) and then eliminating a player (line 25).
This procedure is repeated until the test at line 16 tells us that only one player
remains. At that point we return the player's number at line 30.
The running time of this routine is O ( MN ) because that is exactly the
number of passes that occur during the algorithm. For small M, this running
time is acceptable, although we should mention that the case M = 0 does not
yield a running time of O (0); obviously the running time is O ( N ) . We do not
merely multiply by zero when trying to interpret a Big-Oh expression. Note
that we can replace LinkedList with ArrayList , without affecting the running
time. We can also use a TreeSet , but the cost of construction will not be O ( N ).

We can represent
the players by a
linked list and use
the iterator to simu-
late the passing.

…

13.1.2 a more efficient algorithm

A more efficient algorithm can be obtained if we use a data structure that sup-
ports accessing the k th smallest item (in logarithmic time). Doing so allows us
to implement each round of passing in a single operation. Figure 13.1 shows
why. Suppose that we have N players remaining and are currently at player P
from the front. Initially N is the total number of players and P is 1. After M
passes, a calculation tells us that we are at player (( P + M ) mod N ) from the
front, except if that would give us player 0, in which case, we go to player N .
The calculation is fairly tricky, but the concept is not.

If we implement
each round of
passing in a single
logarithmic opera-
tion, the simulation
will be faster.