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 the first point in the circle and proceeds around the circle in a clockwise 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. For example if n=10 then the order of elimination is 2, 4, 6, 8, 10, 3, 7, 1, 9 and 5
The problem is, without simulation of the above game, try to find out the order of
elimination through means of mathematical formula or a mathematical pattern.
Initially we are given n i.e the number of people in the circle at the start. Give the order of elimination keeping in mind the above conditions and constraints.
In simple words, print the pattern of deaths without using any data structures like arrays and linked lists.
I have prepared the solution after studying http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf . This recursive is mentioned in the above pdf.
int last_man(int n,int x)
{
if(n==1 && x==1)
return 1;
else if(n>1 && x==1)
return 2;
else if(last_man(n-1,x-1)==n-1)
return 1;
else
return last_man(n-1,x-1)+2;
}
X denotes the xth person to die and n is the total number of people initially. Looping this function over all values of x from 1 to n gives us the order of elemination.