Generalized Josephus-Problem

98 Views Asked by At

So the question is based on the Josephus Problem (https://en.wikipedia.org/wiki/Josephus_problem). Additionally to the parameters $n$ and $k$ a third one $m$ is introduced. Instead of calculating the position of the last one being executed (therefore freed), we are asking for the number of the person standing at position $m$ regarding execution. So if the people that are being executed are numbered from $1..n$, what number will the person standing in the initial circle at position $m$ get?

1

There are 1 best solutions below

0
On BEST ANSWER

So writing an algorithm to solve this problem in $\mathcal{O}(n)$ is fairly simple since we only need to account for the position of the person $m$, we can simulate the executions (in pseudocode):

let elim = 1
let pointer = m
let count = n
for i in 1 to n:
   elim = mod(elim + (k-1), count)
   elim = if elim is 0 then count else elim 
   if elim is pointer then return i
   //update position of person
   pointer = if elim < pointer then pointer - 1 else pointer
   count = count - 1
return n

The interesting question is if it is possible to describe this in a mathematical formular (like the recursive solution for the original problem)