Wednesday, August 26, 2009

Josephus Problem

The Josephus problem  is a problem often discussed and seen in CS literature. I got introduced to the problem when I initially started programming and knowing nothing about linked lists and/or recursion had a really hard time solving it.

The problem is stated as:
There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The easiest and most logical way to solve the problem is to simply simulate it using a circular link list.

N is no. of people, M as the count.

struct node {  
int item;
node* next;
};


int simple_simulation(int N, int M)
{
int i;
node *t=new node();
node *x=t;
t->item = 1; t->next = t;

//Construct the list
for (i = 2; i <= N; i++)
{
x = (x->next = new node ());
x->item = i;
x->next = t;
}

//Find the survivor
while (x != x->next)
{
for (i = 1; i < M; i++)
x = x->next;
x->next = x->next->next; N--;
}
return x->item;
}


A better way to solve the problem is through recursion. Its easy to find who is killed first, (Hint: it’s the Mth guy from the start) after that we are left with N-1 total people and the count starts from the new guy who was at M+1th position earlier. Going on like this gives us a simple recursive function:



int formula (int N, int M) 
{
if (N == 1)
return 0;
return (formula (N-1, M) + M) % N;
}


References:

http://en.wikipedia.org/wiki/Josephus_problem

1 comment:

George said...

Hi,

I just wanted to drop a line and say thanks for posting this solution first of all.
But i tried it, and i do want to point out that the recursive function seems to always miss the "survivor's" position by one.

For example, when there are 41 people in the circle and every 3rd person is eliminated, the person in position 31 should be the survivor (1 based not zero). The recursive solutions returns 30 instead of 31. Then i tried it with other values and i found that i always had to add 1 to whatever answer is returned by the recursive solution to get the right survivor.

Thanks.

Related Posts with Thumbnails