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

1 /**
2 * Return the winner in the Josephus problem.
3 * Linked list implementation.
4 * (Can replace with ArrayList or TreeSet).
5 */
6 public static int josephus( int people, int passes )
7 {
8 Collection<Integer> theList = new LinkedList<Integer>( );
9
10 // Construct the list
11 for( int i = 1; i <= people; i++ )
12 theList.add( i );
13
14 // Play the game;
15 Iterator<Integer> itr = theList.iterator( );
16 while( people-- != 1 )
17 {
18 for( int i = 0; i <= passes; i++ )
19 {
20 if( !itr.hasNext( ) )
21 itr = theList.iterator( );
22
23 itr.next( );
24 }
25 itr.remove( );
26 }
27
28 itr = theList.iterator( );
29
30 return itr.next( );
31 }

figure 13.2
Linked list
implementation of the
Josephus problem

Applying this calculation to Figure 13.1, we observe that M is 1, N is ini-
tially 5, and P is initially 1. So the new value of P is 2. After the deletion, N
drops to 4, but we are still at position 2, as part (b) of the figure suggests. The
next value of P is 3, also shown in part (b), so the third element in the list is
deleted and N falls to 3. The next value of P is 4 mod 3, or 1, so we are back at
the first player in the remaining list, as shown in part (c). This player is
removed and N becomes 2. At this point, we add M to P , obtaining 2. Because
2 mod 2 is 0, we set P to player N , and thus the last player in the list is the one
that is removed. This action agrees with part (d). After the removal, N is 1 and
we are done.
All we need then is a data structure that efficiently supports the findKth
operation. The findKth operation returns the k th (smallest) item, for any

The calculation is
tricky because of
the circle.