Solving Josephus Problem Using PHP

Introduction

The Josephus problem or Josephus permutations is a theoretical problem related to a certain counting-out game.

Related Posts:

Josephus problem could be explained similar to below situation:

People are standing in a circle waiting to be executed. Counting begins at a specific position in the circle and proceeds around the circle in a specific direction. After a specified number of people skipped, the next person ia 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 is left in the circle. The only remaining person is then freed.

Prerequisites

PHP 7.4

Josephus Implementation

I am going to implement Josephus problem using PHP programming language and the source code is given below:

<?php

function josephWinner($noOfPeople, $remStartPos) {
	$arr = array();
	for($i = 0; $i < $noOfPeople; $i++) {
		array_push($arr, ($i+1));
	}

	$calRemPos = $remStartPos - 1;
	$iterations = $noOfPeople - 1;
	while($iterations > 0) {
		unset($arr[$calRemPos]);

		$arr = array_values($arr);

		$calRemPos += $remStartPos - 1;
		if ($calRemPos > (count($arr) - 1)) {
			$calRemPos = $calRemPos % count($arr);
		}
		$iterations--;
	}
	return current($arr);
}

Analysis of the Josephus Problem

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 they are left with the list something like – 1 2 4 5.

Now again you need 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 need 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.

Testing Josephus

I have invoked the above function using the following values:

<?php
$winner = josephWinner(5, 3);
echo ('winner is ' . $winner);
echo nl2br("\n");
$winner = josephWinner(10, 3);
echo ('winner is ' . $winner);
echo nl2br("\n");
$winner = josephWinner(5, 2);
echo ('winner is ' . $winner);
echo nl2br("\n");
$winner = josephWinner(7, 3);
echo ('winner is ' . $winner);
echo nl2br("\n");

The output comes after running the above code:

winner is 4
winner is 4
winner is 3
winner is 4

Source Code

Download

Roy Tutorials