A Dynamic Programming Solution to the Josephus Problem

I found an interesting problem in the book Data Structures and Algorithms in Java known as the Josephus Problem. In the book, there is a naive solution using the Round-Robin scheduling algorithm; however, I considered dynamic programming to solve this problem discretely.

A Little Background on the Josephus Problem

During the siege of Yodfat, Josephus was trapped in a cave with forty other soldiers while Roman soldiers waited outside. Instead of submitting to the Romans, they decided to commit suicide starting with every third man. In the end, Josephus and another man were the last men standing. Through some coercion, Josephus was able to prevent the morbid game from continuing at that point. Thus, they surrendered to the Romans, escaping death!

Here is a quote from Josephus in his book, outlining the situation:

“since it is resolved among you that you will die, come on, let us commit our mutual deaths to determination by lot. He whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself.”

Now, the problem here is similar to a counting-out game such as eeny-meeny-miny-moe except that the penalty of being chosen is death. Intense game they play.

Let’s break it down now and try to find the last man standing, for they shall be graced with life.

Dynamic Programming solutions usually have three functions; however, they are often implicit.

Objective Function
The algorithm which defines our objective; finding the last man standing.
Policy Function
Functions which represent control variables as a function of the current state; finding the next man to kill.
Value Function
The function which defines the best possible value for the given objective; finding the current position of a man to kill.

Programming the Solution in Java

public class JosephusProblem {
// Objective function
public static int findLastManStanding(int population, int killStep) {
// Implement the algorithm logic
}
}

When writing this Dynamic Programming solution, it’s best to start from the objective function because we know what it is: find the last man standing given the population and the the number of steps before suicide.

public class JosephusProblem {
// Policy function
public static int nextMan(int currentManToKill, int killStep, int population) {
return (currentManToKill+ killStep) % population;
}

// Objective function
public static int findLastManStanding(int population, int killStep) {
// Implement the algorithm logic
}
}

It’s also necessary to understand the policy function. We must find the next man to kill starting from a given state which is the current position of the current man to kill. Using some mathematics and logic, we derive the next man to kill.

The modulus operator % is an important mathematical concept here because we cannot kill a man beyond the population size. This err can be avoided using the modulus operator, thereby starting from the beginning of the population when the next man to kill is out of bounds such as a circularly linked list.

public class JosephusProblem {
// Policy function
public static int nextMan(int currentManToKill, int killStep, int population) {
return (currentManToKill+ killStep) % population;
}

// Objective function
public static int findLastManStanding(int population, int killStep) {
// Value function
int[] manToKill = new int[population + 1];
manToKill[0] = nextMan(0, killStep, population);
}
}

Afterwards, we construct our value function; however, our value function isn’t necessarily a method. Instead, the function is represented as an array (or table) to quickly calculate and retrieve values dependent on previous sub-problems; the position of next man to kill is dependent on the position of the previous man killed.

The idea of using arrays or tables to store commonly calculated values is known as memoization.

Because the value function returns the man to kill given the current kill step, we can simply use the bottom-up method of dynamic programming to determine the man to kill at the final population size. Knowing that the first man to kill is simply the value of the killStep, then we can instantly append that sub-problem solution to our value function.

public class JosephusProblem {
// Policy function
public static int nextMan(int currentManToKill, int killStep, int population) {
return (currentManToKill + killStep) % population;
}

// Objective function
public static int findLastManStanding(int population, int killStep) {
// Value function
int[] manToKill = new int[population + 1];
manToKill[0] = nextMan(0, killStep, population);

for (int i = 1; i <= population; i++)
manToKill[i] = nextMan(manToKill[i - 1], killStep, population);
}
}

Here we must solve each sub-problem for the next man to kill iteratively until the number of men we have killed equal to population.

public class JosephusProblem {
// Policy function
public static int nextMan(int currentManToKill, int killStep, int population) {
return (currentManToKill + killStep) % population;
}

// Objective function
public static int findLastManStanding(int population, int killStep) {
// Value function
int[] manToKill = new int[population + 1];
manToKill[0] = nextMan(0, killStep, population);

for (int i = 1; i <= population; i++)
manToKill[i] = nextMan(manToKill[i - 1], killStep, population);

return nextMan(manToKill[population], killStep, population);
}
}

There's a little trick going on here to find the last man standing. We've been solving the next man to be killed; thus, the last man standing should be the next man to be killed at the end of our loop; however, because the number of people alive at the end of each suicide decreases by one, we must consider the offset for which the true last man standing.

I won't complete the proof here, but the offset for the true last man standing is actually proportional the killStep!

Analysis & Conclusion

The running time of this solution is much quicker than the Round-Robin scheduler suggested using queues which yields a running time of $O(nk)$ where $n$ is the population and $k$ is the kill step.

This algorithm constructed runs in linear time i.e. $O(n)$ where $n$ is the population. This is trivially solved by noting the single for-loop in the algorithm created.

In a situation where the counting-game determines a suicide position, the linear running time of this algorithm could save a life.