Count Out (The Josephus Problem)

This problem was given in class.

n children are arranged in a circle and m words are used to count out the children in rounds. The last child wins.


The Problem
Given n children and m words and a starting position (say child 1), who wins?


This is a variation of the Josephus problem.


Here is a Java solution. Simply call josephus(n, m, s) to run.



   /**
     * Performs the counts in rounds and returns the index of the winner.
     * circle is assumed to be an array of size n.
     * @param n The number of children
     * @param m The number of words
     * @param start The starting position
     * @return
     */
    private int josephus(int n, int m, int start){
        initialize(n);
        int i = start;
        while(circle[i] != i){            
            int pos = i;
            int prev = pos;
            for(int j = 1; j < m; j++){
                prev = pos;
                pos = circle[pos];
            }
            //remove current position
            circle[prev] = circle[pos];
            i = circle[pos];
        }
        return i;
    }


The initialize(n) method simply initializes the circle array  so that each  position 0 points to position 1, position 1 points to position 2 etc. That is, position i points to position i + 1. This indicates that the circle is full. To drop a child out at position i, then position i - 1 will point to position i + 1.



    /**
     * Initializes the circle array.
     * m <= n
     * @param n Number of persons
     *
     */
    private void initialize(int n){
        circle = new int[n];
        for (int i = 0; i < n - 1; i++){
            circle[i] = i + 1;
        }
        circle[n-1] = 0;
    }