Saturday, 24 December 2016

Josephus Problem, my exploration

Intro is taken from Wikipedia. In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.
(Following picture is taken from a Numberphile video on YouTube)




Here, counting will in done in clockwise manner. n will be the number of people in the circle waiting to be executed. k will decide which person should die such that (k - 1) people will be skipped and kth person will be killed. For example, if k =  2 then 1st person will skip himself and will kill the 2nd person, then 3rd person will skip himself and kill the 4th person and so on.

For k = 1, everybody will kill himself and nth person will be the answer since that position will be the one on which last execution is possible.
For any k > 1, algorithm is very easy to write using queues, linked lists, arrays and dynamic  programming, but we will be looking at the mathematics side of the problem for k = 2.

Suppose, initially there are 2n persons in the circle. We start clockwise with first person killing 2nd person(taking k = 2 and first person could be anybody but once chosen should not change). After the first round, all the even numbered people will be killed and n people with odd numbering will remain(namely 1, 3, 5, ..., 2n - 1). We can rename these people 1, 2, 3, ..., n. After the renaming, we will find the answer to this new problem with n person. Let the answer to this new problem is yth person(y is any natural number less than or equal to n). So the answer to our original problem with 2n persons will be (2*y - 1)th person.

Therefore, using recursion we can write, M( 2*n ) = 2*M( n ) - 1. Here, M( n ) is the answer to above problem with k = 2 and n persons. M( 1 ) = 1.

Similarly, for 2*n + 1 persons, we can find, M( 2*n + 1 ) = 2 * M( n ) + 1. Again, M( 1 ) = 1.

Before I state my foolish conclusion, I must state that there is another solution to this problem with order of one time complexity.

Just moving the last 1-bit in n's binary form to the first position will give us the answer. For example,

n = 41 = 32 + 8 + 1 = 0b(101001)
answer = 0b(010011) = 19
OR
n = 19 = 16 + 2 + 1 = 0b(10011)
answer = 0b(00111) = 0b(111) = 7
OR
n = 7 = 4 + 2 + 1 = 0b(111)
answer = 0b(111) = 7

But how are we getting the answer just by shifting 1 bit of the the problem's input. Wikipedia has the answer but I am also stating my result here.

If we apply the above two recursion equations to solve this problem, we will get something like this :
M( n ) = 2^k + (2^p1 + 2^p2 + ...) - (2^q1 + 2^q2 + ...) ± 1. The last one is added is n is odd and subtracted if n is even. This plus-minus thing for 1 need not be specified. I just wanted to show that I invested a lot of time in this problem !

Observe carefully :
M(14) = 2 * M(7) - 1
          = 2 * (2 * M(3) + 1) - 1
          = 4 * (2 * M(1) + 1) + 2 - 1
          = 8 + 4 + 2 - 1
and 14 = 8 + 4 + 2.
Again observe carefully :
M(41) = 2 * M(20) + 1
          = 2 * (2 * M(10) - 1) + 1
          = 4 * (2 * M(5) - 1) - 2 + 1
          = 8 * (2 * M(2) + 1) - 4 - 2 + 1
          = 16 * (2 * M(1) - 1) + 8 - 4 - 2 + 1
          = 32 - 16 + 8 - 4 - 2 + 1
and 41 = 32 + 8 + 1.
What do we observe here? State the given n in its sum of power of two like 19 = 16 + 2 + 1. Then the answer will contain these power of two and negative of sum of power of two which are not in n less then the highest power already present in n(If you get this, don't worry, I explained it again down under). M(19) = 16 - 8 - 4 + 2 + 1 = 7. Tada!

If n = 2 ^ 5 + 2 ^ 3 + 2 ^ 2 then it do not have 2 ^ 4, 2 ^ 1 and 2 ^ 0. So M( n ) = 2 ^ 5 + 2 ^ 3 + 2 ^ 2 - 2 ^ 4 - 2 ^ 1 - 2 ^ 0. This is what happens if we take the last 1-bit in a binary number and put it as the first bit of the same number.

I know everything was boring in this blog but I am not getting time to write something more useful. Sorry!

No comments:

Post a Comment