Solving Josephus Problem Using Python

Introduction

In this example, I am going to show you how to solve Josephus problem using Python. The Josephus’ Problem can be stated as follows:

There was a group of 41 Jewish soldiers surrounded by Roman army, and they didn’t want to get caught. So, they sat down in a circle and came up with an algorithm. Everybody had a sword, and starting from person #1 in the circle, everybody will kill the next living person on the left. So, #1 will kill #2. #3 will kill #4, #5 will kill #6 and so on. The last living person will have to commit suicide to avoid getting caught by Romans.

The soldier called Josephus preferred to be caught over committing suicide. So, in the group of 41 soldiers, he chose the location where he will be the last person living.

The pictorial representation of the Josephus problem can be shown in the below image:

In the above image the execution starts from 2 and finally the free person will be 11.

Related Posts:

Prerequisites

Python 3.x

Josephus Implementation

The Josephus problem implementation in Python is given below:

def josephus(num_people, rem_pos):
    temp_pos = rem_pos - 1
    people = []
    
    for i in range(num_people):
        people.append(i+1)
    
    iteration = num_people - 1
    
    while iteration > 0:
        people.pop(temp_pos)
        temp_pos += rem_pos - 1
        if(temp_pos > len(people) - 1):
            temp_pos = temp_pos % len(people)
        iteration = iteration - 1
    
    return people[0]

Testing Josephus

You can invoke the above Python function for the following values:

print('Winner is %d' % josephus(5, 3))
print('Winner is %d' % josephus(10, 3))
print('Winner is %d' % josephus(5, 2))
print('Winner is %d' % josephus(7, 3))

The above print() function will give you the following output:

Winner is 4
Winner is 4
Winner is 3
Winner is 4

Let’s take an example of there are 5 people in a circle and execution starts clockwise at position 3, so I will find out the winner of the game.

So there are five people – 1 2 3 4 5 and execution starts clockwise at position 3. Therefore if you kill 3 then are left with the list something like – 1 2 4 5.

Now again you have to kill the person at position 3 clockwise counting from the last killed person.

Now you need to execute the person at position 1. So executing the person at 1 you are left with the list 2 4 5. After executing another person you get list 2 4.

Now you are left with 2 persons in the list. So you have to calculate the position wisely to execute the person. Therefore the calculated position would be (starting position of the execution)%(no of people remaining in the list less than starting position) = 3%2 = 1.

So finally the winner is 4.

Source Code

Download

Roy Tutorials