Using Java Queue to Solve the Josephus Problem

Question

4.3.39 Josephus problem. In the Josephus problem from antiquity, n people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to n 1) and proceed around the circle, eliminating every mth person until only one person is left. Leg- end has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus that takes two integer command-line arguments m and n and prints the order in which people are eliminated (and thus would show Jose- phus where to sit in the circle).

% java Josephus 2 7 
1 3 5 0 4 2 6 

Implementing Steps

In this solution, we are going to use the Queue as the position container. Using the Dequeue and Enequeue methods to iterate all the positions. Keep doing this until all of the positions are popped out.

Here goes the steps:

1. Create a Integer Queue.
2. Iterate all the items.
3. Find and remove the item at the eliminated position.
4. If the Queue is empty, done.

Implementing Steps

1. Copy the Stack code on Java Queue Implementation page.
2. Save the Queue code as Queue.java
3. Copy the following code and save as JosephusQueue.java

Solution

/******************************************************************************
 *  Compilation:  javac JosephusQueue.java
 *  Execution:    java JosephusQueue args
 *  Dependencies: Queue.java @link https://mrtan.me/post/17.html
 *
 *  Using Queue to print out the ordered eliminated positions
 *  in Josephus Problem.
 *
 *  % java JosephusQueue 2 7
 *  1 3 5 0 4 2 6
 *
 ******************************************************************************/

class JosephusQueue {
    public static void main(String[] args) {
        int position = Integer.parseInt(args[0]);
        int count = Integer.parseInt(args[1]);

        printJosephusPositions(count, position);
    }

    public static void printJosephusPositions(int count, int position) {
        Queue<Integer> queue = new Queue<Integer>();
        for (int i = 0; i < count; i++) {
            queue.enqueue(i);
        }

        while(!queue.isEmpty()) {
            // The eliminated position counted from 1.
            for (int i = 1; i <= position; i++) {
                int eliminatedPosition = queue.dequeue();

                if (i == position) {
                    System.out.print(eliminatedPosition + " ");
                    break;
                }

                queue.enqueue(eliminatedPosition);
            }
        }
    }
}

Output

-> java JosephusQueue 2 7
1 3 5 0 4 2 6

The time complexity of this method is O(n).