An explanation on Josephus problem aka Suicide Circle problem
Josephus problem is one of the numberphile in Computer Science. It is also called as suicide circle problem because of the history behind it.
Flavius Josephus, a Jewish soldier, and historian lived in the first century. He fought along with 39 soldiers against Roman in a war, where they have trapped in a cave. The soldiers except Josephus decided to take their lives instead of getting killed by the Romans. So they formed a circle known as suicide circle. Each person standing on the circle should kill the person next to them and hand over the weapon to next living soldier. Till the last survivor, the game should go on.
Josephus decided to live and found a way to escape from the suicide circle. He calculated the position which other soldiers cannot kill. He himself placed in 17th position and escaped from the suicide circle.
The Actual Josephus problem
In a circle where n people stand and k is the skipping interval, find which position will come last. The problem is taken based on the 1-index people standing on top of it.
Let’s say a circle made up of 4 people and the skipping interval is 2. Keep in mind, it is 1-index and interval starts from the active index.
1* 2 3 4
The number 1 will count off number 2 and 3 will become active.
1 x 3 * 4
Number 4 will count off from the circle and number 1 will become active,
1* x 3 x
Number 3 will count off, then 1 will become active and the last survivor of the game.
1* x x x
In each iteration n will be reduced by 1, i.e., n will become n-1 and the indices will change respectively.
There is already a solution available based on dynamic programming, the following equation derived to solve this problem.
f(n,k) = ((( f(n-1), k ) + k -1 ) % n) +1, where f(1, k) = 1.
Shall we substitute the values of our problem?
Lets take n = 4 and k = 2 for simplicity, so the equation would become
f(4,2) = ((( f(4–1), 2 ) + 2 -1 ) % 4) +1
to solve we need f( 3, 2 )
f(3,2) = ((( f(3–1), 2 ) + 2 -1 ) % 3) +1
to solve this we need f( 2, 2 ),
f(2,2) = ((( f(2–1), 2 ) + 2 -1 ) % 2) +1
we know that, f(1,k) = 1 hence f(1,2)=1. Now substitute the values
f(2,2) = 1
f(3,2) = 3
f(4,2) = 1
Hence the survivor is number 1.
Below is the C# implementation of the same.
Originally published in Trendy Tech News.