Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Explanation for recursive implementation of Josephus problem

EDIT: n is the number of persons. k is the kth person being eliminated. So for k=2, every 2nd person is getting eliminated.

int josephus(int n, int k)
{
 if (n == 1)
  return 1;
else
   return (josephus(n - 1, k) + k-1) % n + 1;
}

The code is as simple as it could be. But somehow I am unable to understand this problem (which is a little embarassing to be honest).

The way I am trying to understand it is,

  1. josephus(n,k) gives the final solution for a population of size n and step size k.
  2. josephus(n,k) can be calculated if we know the solution for josephus(n-1,k). That is in my opinion "optimal substructure property" of dynamic programming.
  3. I get that we need to do a MOD N so that in case number goes past n, it will again start counting from 1. (i.e. ensure that addition behaves like we are counting in a circle). But why did we add this "k-1"?

The main question is if we know the correct solution of josephus(n-1,k), how are we calculating the solution to josephus(n,k). We have effectively added one more person to the population and somehow adding this k-1 value is giving me the correct solution (let's ignore mod for a moment).

Can anyone explain this to me that how is the optimal substructure property holding at each step in the problem?

like image 253
rents Avatar asked Aug 02 '15 19:08

rents


People also ask

Is Josephus problem recursive?

The problem has the following recursive structure. After the first person (kth from the beginning) is killed, n-1 persons are left. So we call Josephus(n – 1, k) to get the position with n-1 persons.

What is the answer to the Josephus problem?

A simple approach to solve this problem is to find the position of the step which would be called after each execution. Therefore, given N persons, and skipping K persons during their deletion, N – 1 persons will be left. Therefore, we need to call the recursive function for N – 1 and K for the next iteration.

What is Josephus problem in data structure?

Problem statement of Josephus Problem N people are standing in a circle waiting to get executed, and counting starts from a certain point in the circle, in a specific direction, either clockwise or counterclockwise. After skipping k people, the next person gets executed.

What is the time complexity of the Josephus problem Josephus n k )?

The time complexity is O(N).


1 Answers

The key insight that made this solution make sense for me is the following: the result of josephus(n, k) is best not thought of as the number that is the Josephus survivor, but rather as the index of the number that is the Josephus survivor. For example, calling josephus(5, 2) will tell you the index of the person out of a ring of five that ends up surviving.

With that intuition in mind, let's think about how the Josephus problem works by looking at a concrete example. Suppose we want to know josephus(n, 2). You can imagine we have n people lined up like this:

1 2 3 4 5 ... n

The first thing that happens is that person 1 kills person 2, as shown here:

1 X 3 4 5 ... n

Now, we're left with a subproblem of the following form: there are n-1 people remaining, every other person is going to be killed, and the first person who will be doing the stabbing is person 3. In other words, we're left with a ring of people shaped like this:

3 4 5 ... n 1

with k = 2. Now, imagine that we make a recursive call to josephus(n - 1, 2), since we have n - 1 people. This will give back the index of who survives in a line of n - 1 people. Given that we have the index of the person who will survive, and we also know who the starting person is, we can determine which person will be left. Here's how we'll do it.

The starting person in this line is the person who comes right after the person who was last executed. This will be person 3. The 1-indexed position of the survivor in the ring of four people is given by josephus(n - 1, 2). We can therefore walk forward josephus(n - 1, 2) - 1 positions, wrapping around the ring if necessary, to get to our final position. In other words, the survivor is given by position

 (3 + josephus(n - 1, 2) - 1) % n

There's a problem with this above formula, though. If we are indeed using one-indexing, what happens if the final survivor is at position n? In that case, we'd accidentally get back position 0 as our answer, but we really want position n. As a fix to this, we'll use a trick for using mod to wrap around with one-indexing: we'll take the inside quantity (the one-indexed position) and subtract one to get the zero-indexed position. We'll mod that quantity by n to get the zero-indexed position wrapped around. Finally, we'll add back one to get the one-indexed position, wrapped around. That looks like this:

(3 + josephus(n - 1, 2) - 2) % n + 1

The -2 term here therefore comes from two independent -1's: the first -1 is because josephus(n - 1, 2) returns a one-indexed index, so to step forward by the right number of positions we have to take josephus(n - 1, 2) - 1 steps forward. The second -1 comes from the fact that we're using one-indexing rather than zero-indexing.

Let's generalize this to work for arbitrary k, not just k = 2. Suppose we want to know josephus(n, k). In that case, person 1 will stab person k, leaving us with an array like this:

1 2 3 ... k-1 X k+1 ... n

We now essentially need to solve a subproblem where person k+1 comes first:

k+1 k+2 ... n 1 2 ... k-1

So we compute josephus(n - 1, k) to get the one-indexed survivor of a ring of n - 1 people, then shift forward by that many steps:

(k+1 + josephus(n - 1, k) - 1)

We need to worry about the case where we wrap around, so we need to mod by n:

(k+1 + josephus(n - 1, k) - 1) % n

However, we're one-indexed, so we need to use the trick of subtracting 1 from the inside quantity and then adding 1 at the end:

(k+1 + josephus(n - 1, k) - 2) % n + 1

which simplifies to

(k-1 + josephus(n - 1, k)) % n + 1

which is equivalent to

(josephus(n - 1, k) + k-1) % n + 1

as in the solution code.

To summarize: the k-1 term comes from starting at position k+1, adding in josephus(n - 1, k) - 1 to shift forward the appropriate amount, then subtracting one and adding one back in at the end to do the correct wraparound.

Hope this helps!

like image 122
templatetypedef Avatar answered Sep 30 '22 15:09

templatetypedef