Explaining the Josephus Algorithm

I came across this interesting algorithm called the Josephus Problem while doing some research, and it really started to make me think about how I approach problem-solving. At the start, the problem presented was seemingly quite difficult to solve, however the more I worked through the problem I found the solution could be eloquently expressed with a few lines of code.

Oh look … a tree made from recursion

The Josephus Problem

Named after a Jewish historian named Flavius Josephus, it was reported he came up with this problem after a battle between Roman and Jewish forces in the 1st century.

He, a companion, and others, ended up being trapped in a cave surrounded by Roman soldiers. Instead of surrendering to the foreign soldiers and favouring to kill themselves over being murdered , the men (N) formed a circle, set a specified direction and start location, and then chose a random number (k) from a lot.

The man at that position in the circle who’s number was chosen would be killed by the man who was k positions down from him. This would go on until there was only one man left.

# An example of the circle with 10 people (N = 10)
# The number 4 was chosen (k = 4)
# First, the 4th person would be killed
[1 2 3 X 5 6 7 8 9 10]
# Second, the 8th person would be killed
[1 2 3 X 5 6 7 X 9 10]
# Third, the 2nd person would be killed ... need to loop
[1 X 3 X 5 6 7 X 9 10]
# Fourth, the 6th person would be killed
[1 X 3 X 5 X 7 X 9 10]
# Fifth, the 10th person would be killed
[1 X 3 X 5 X 7 X 9 X]
# Sixth, the 5th person would be killed ... because the 4th 
# is already gone
[1 X 3 X 5 X 7 X 9 X]
# This would continue until only the person starting at
# the 5th position was left

Only one person is supposed to remain at the end, the final person at the final index of the circle. Luckily for Josephus he knew this game well, as he and his companion were placed correctly in the circle so only the two of them survived.

But how did he know where to place himself and his companion? This is the Josephus Problem.

Pseudocode Solution

How could have Josephus solved this huddled in a cave?

Let’s start with the two inputs, the number of people in the circle N and the number that are skipped every time k. By knowing k means we know the number of people skipped between the person who is dying and the next person dying is k-1.

Keep in mind we are using a one-indexed array, and will account for a zero-indexed array later in the problem. Even though the problem states the people are set up in a circle, you’ll have to traverse an array and loop over it if you’re going to be solving this with code. So think of the problem in those terms.

# Assume N = 10, k = 3
[1 2 3 X 5 6 7 8 9 10]
# We know the person in index 3 will be removed
# So between the first survivor and the person removed
# there are (k - 1) = (3 - 1) = 2 people.

Now that we know who is going to be removed in the first run through, we can start to look if a pattern will appear. Let’s remove only a single person from the circle, and designate the person right after that position as the survivor.

# Back to our example with N = 10, but k = 2
# Now the circle looks like this without position 2
# 3 is the survivor
[1 X 3 4 5 6 7 8 9 10]

Now we know there are N — 1 people left in our circle, and we’re still removing every kth person. We can reframe the problem by shifting down the starting position of the circle, as we know the person in the first index (1) has been skipped over and the next person to be removed (4) will be removed by 6, so our next survivor is 3.

# After the first person is removed "shift" the array; N=9
[3 4 5 6 7 8 9 10 1]

Before we shifted the array, our survivor 3 was in the 3rd position in the circle and now is in the 1st. Now we know the first index of the first person who will survive.

Can we do the same for the next part?

# After the second person is removed "shift" the array;  N=8
[5 6 7 8 9 10 1 3]

We’ve shifted the array again, and our current survivor 5 is currently in the 1st index, where previously they were in the 3rd index, and before that was in the 5th index.

# This is how each iteration of the problem looks
1 2 3 4 5 ... k k+1 k+2 ... N
# k is removed
# k+1 is the survivor
# N is the current total of the circle
# New shifted array to solve for our new survivor
k+1 k+2 ... N 1 2 3 4 5 ... k-1

A small pattern is emerging, where the current survivor will be in the first index and has been moving towards this index by k+1 every time someone is removed from the array. Now, we need to create a function where we’re always returning to the previous location of the final survivor given we know the final survivor will eventually be the only element left in our array.

So now we know the final location of the survivor is 1, and we can work out way back from this location.

def josephus(N, k):
  if N == 1:
return 1
  else:
# More code here

The key is to create an equation where we’re constantly looking for our final survivor’s position throughout the array every time someone is removed. We want to keep returning that location as we increase N, until we have the survivor’s initial position in the array. Meaning we can solve this problem recursively, as we know when N=1 our function should return 1 and when N=n our function should return the final position.

# Our starting position is 1 in the array and we need to shift
# our survivor's previous position
# Remove k
1 2 3 4 5 ... k-2 k-1 k k+1 k+2 ... N-2 N-1 N
# Our new series with k+1 as the survivor
k+1 k+2 ... N-2 N-1 N 1 2 3 ... k-1

But, how do we know the previous position(s) of our survivor before they are actually the final survivor? We need to figure out positions when N=2, N=3, all the way up to N=n.

# Final survivor's second last location
k+1       <-- The survivor always starts here
1 <-- The survivor final (previous) location
(-1) <-- Accounting for the shrinking array

So we need to add up these values to find the previous position for each value of N=n and form our final equation. The only part of the three values above we need to change to form our equation is The survivor final (previous) location, which starts at 1, and changes every iteration.

So the result (position) we want to be returned after every iteration is:

(k+1) + f(N-1, k) - 1

Breaking Down The Equation

We know our final survivor was previously at position k+1 given they are now in position 1 as the only person left. However, in the previous position, the array was one person larger. Meaning we need to account for this shift by subtracting 1 from our equation.

As well, because we’re going to wrap around the end of the circle and pass over indexes previously skipped over, we need to use the mod operator (%) to get the associated indexes.

((k+1) + f(N - 1, k) - 1) % N

The final step is to account for the array not being indexed at zero, so we need to add 1 to our final answer which means balancing the LHS with the RHS of the equation. What can be confusing about this result is traversing a zero-indexed array, but returning a one-indexed value.

# Final part of the equation
(k-1 + f(N - 1, k)) % N + 1

Actually quite simple once it is solved.

A Full Example

Now that we have the equation, here is a full but trivial example with answers for each iteration of the solution.

# Who is our final survivor when N = 5, k = 2 ?
# Spoiler ... it is the person starting at the third position

Let’s see how this plays out backwards using the equation from above.

# Starting from the final position
[3] <-- Our survivor
[3 5]
[5 1 3]
[3 4 5 1]
[1 2 3 4 5] <-- Initial array
# What position is our final survivor in?
1
1
3
1
5
# What are the results of our equation above?
# (k-1 + f(n - 1, k)) % n + 1
1
1 = (2 - 1 + 1) % 2 + 1
3 = (2 - 1 + 1) % 3 + 1
1 = (2 - 1 + 3) % 4 + 1
3 = (2 - 1 + 1) % 5 + 1

Putting It All Together

Now that we are comfortable with our maths and results, let’s put everything together in a recursive algorithm.

def josephus(N, k):
"""
:param n: The number of objects in the circle (array)
:param k: The number of skips after an object is removed
:return: The position of the final object left
"""
  if N == 1:
return 1
  else:
(k-1 + josephus(n - 1, k)) % n + 1

By starting with the final index and working backwards, we were able to break down the simplicity of our equation. At the start, we were given all the puzzle pieces for solving our problem, and it just took some reframing to get the right answer.

Final Thoughts

I quite enjoyed going through this problem as most of the recursion articles I read used a Fibonacci sequence to show the application of the concept. The Josephus problem provided some diversity in the application of recursion.

However, most importantly was the thought process of how to break down this algorithm problem from its conclusion back through each step to the start. Without that, I don’t think this exercise would have been helpful.

Additional Links