Josephus Problem in Data Structure

Now we will see an example where circular link list is very useful. This is Josephus Problem. Consider there are 10 persons. They would like to choose a leader. The way they decide is that all 10 sit in a circle. They start a count with person 1 and go in clockwise direction and skip 3. Person 4 reached is eliminated. The count starts with the fifth and the next person to go is the fourth in count. Eventually, a single person remains.

You might ask why someone has to choose a leader in this way. There are some historical stories attached to it. This problem is also studied in mathematics. Let’s see diagrammatically.

 

We have ten numbers representing the ten persons who are in a circle. The value of M shows the count. As the value of M is three, the count will be three. N represents the number of persons. Now we start counting clockwise. After counting up to three, we have the number four. The number four is eliminated and put in the eliminated column.

Eliminated

After eliminating the number four, we will start our counting from number five. Counting up to three, we have number eight which is eliminated and so on.

The process is continued and In the end, only number five will remain intact.

 

If we have ten persons (N = 10) in a circle and eliminate after counting up to three (M = 3). If we start our count from one, who will be the leader? We have studied this earlier and know that the person who is sitting at the fifth position will become the leader.

Suppose if the value of N is 300 or 400 and the value of M is 5 or 10. Now who will be the leader? This is a mathematical problem where we can change the values of N and M. There is a formula where the values of N, M are allotted. You can calculate who should become the leader. Here we will not solve it mathematically. Rather, it will be tackled as a computer problem. If you analyze the pictures shown above, it gets clear that this can be solved with the circular link list. We arrange these numbers in a circularly-linked list, point the head pointer at the starting number and after calling the next method for three times, we will reach the node which is to be removed. We will use the remove method to remove the node. Then the next method is called thrice from there and the node is removed. We will continue this till we have only one node.

We are not concerned with the NULL pointers, internal to link list. However, if you want to solve this problem and choose the best data structure, then circular link list is the best option. We can also use the list to solve this.

Let’s see the code of the program by which we can solve this problem. The code is as under:

/*This program solves the Josephus Problem */ #include <iostream.h> #include "CList.cpp" //contains the circularly-linked list definition // The main method void main(int argc, char *argv[]) { CList list; // creating an object of list int i, N=10, M=3; for(i=1; i <= N; i++ ) list.add(i); // initializing the list with values list.start(); // pointing the pointers at the start of the list // counting upto M times and removing the element while( list.length() > 1 ) { for(i=1; i <= M; i++ ) list.next(); cout << "remove: " << list.get() << endl; list.remove(); } cout << "leader is: " << list.get() << endl; //displaying the remaining node }

We have included the “CList.cpp”. It means that we are using the circularly-linked list. In the main method, CList is called to create a circular link list as CList list; After this, we assign the values to N and M. We have used for loop to add the nodes in the list. When this loop finishes, we have ten nodes in the list having values from 1 to 10. But here a programmer may not pay attention to the internal details of the list. We have created a list and stored ten numbers in it. Then we moved the pointers of the list at the start of the list using the start method. It means that the pointers are pointing at the position from where we want to start the counting of the list.

There is a while loop that will continue executing until only one node is left in the list. Inside this loop, we have a for loop. It will execute from 1 to M. It has only one statement i.e. list.next(). This will move the pointer forward three times (as the value of M is 3). Now the current pointer is at the 4^th node. We called the remove method. Before removing the node. Again we come into the while loop, now the length of the list is 9. The ‘for loop’ will be executed. Now the list.next() is not starting from the start. It will start from the position where the current pointer is pointing. The current pointer is pointing at the next node to the node deleted. The count will start again. The list.next() will be called for three times. The current pointer will point at the 8^th node. Again the remove method will be called and the current pointer moved to the next node and so on. The nodes will be deleted one by one until the length of the list is greater than one. When the length of the list is one, the while loop will be terminated. Now only one node is left in the list i.e. the leader. We will display its value using the get method.

We can change the values of M and N. Similarly, these values can be read from the file or can use the command line arguments to get values. There are many variations of this problem. One variation is that the value of M keeps on changing. Sometimes, it is 3, sometimes 4 or 5 and so on. Due to this, it will become difficult to think that who will become leader. Make a picture in your mind that ten persons are sitting in a circle. Every time the value of M is incremented by one. Now try to ascertain which position you should sit to get chosen as a leader.

The code of the program is given below.

#include "CList.cpp" void main(int argc, char *argv[]) { CList list; int i, N=10, M=3; for(i=1; i <= N; i++ ) list.add(i); list.start(); while( list.length() > 1 ) { for(i=1; i <= M; i++ ) list.next(); cout << "remove: " << list.get() << endl; list.remove(); } cout << "leader is: " << list.get() << endl; }

In the program, we include the file of the class CList and create its object i.e. list. Then we solve the problem by using the add, start, length, next, remove and get methods of the class CList.

In the program, we have included already-defined data structure CList. After defining its different methods, we have an interface of Clist. There is no need to be worry about the nature of the list i.e. whether it is linked list, doubly linked list or an array. For us, it is only a list to be manipulated according to our requirement. You will see that a programmer may use different methods of the list object to solve the problem. We add elements to the list by a simple call of add method and go to the first element of the list by start method. Here, the length method is used in the condition of the while loop. Then we remove elements from the list and use the next, get and remove methods during this process. We get the current element by using the get method, then remove it by calling the remove method and then go to the next element by the method next. This way, all the elements are removed from the list except one element, called the leader. This one element remains there as we execute the while loop one less than the length of the list.

In singly linked list, the ‘next’ returns false when it reaches to the last node due to the fact that the next field of the last node is set to NULL. But in a circularly linked list there is no NULL. It will be there only when there is no node in the list.

Technorati Tags: data structure,data structure and algorithm tutorial,ds tutorial,linked list tutorial,linked list implementation,linked list,link list,programming,linked list in c++,josephus problem,josephus problem in data structure