Solving Josephus Problem using PHP

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

If you need to solve the Josephus problem using Java, please read here Solving Josephus Problem using Java

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.

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);
}

$winner = josephWinner(5, 3);
echo ('winner is ' . $winner);
echo "n";
$winner = josephWinner(10, 3);
echo ('winner is ' . $winner);
echo "n";
$winner = josephWinner(5, 2);
echo ('winner is ' . $winner);
echo "n";
$winner = josephWinner(7, 3);
echo ('winner is ' . $winner);
echo "n";

?>

Ananlysis of the game

Let’s take an example of there are 5 people in a circle and execution starts clockwise at position 3, so we 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 we kill 3 then are left with the list something like – 1 2 4 5.

Now again we have to kill the person at position 3 clockwise counting from the last killed person. Now we need to execute the person at position 1. So executing the person at 1 we are left with the list 2 4 5. After executing another person we get list 2 4.

Now we are left with 2 persons in the list. So we 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.

The output comes after running the above code

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

Thanks for reading.

Soumitra Roy Sarkar

I am a professional Web developer, Enterprise Application developer, Software Engineer and Blogger. Connect me on JEE Tutorials Twitter Facebook  Google Plus Linkedin

Leave a Reply

Your email address will not be published. Required fields are marked *