How can I find the order of elimination in Josephus Problem in C?

user_13731436 0
Viewed 374

The Josephus can be solved with the following algorithm:

int josephus(int n, int k)
{
  if (n == 1)
    return 1;
  else
    return (josephus(n - 1, k) + k-1) % n + 1;
}

However, I would also like to know who was the i-th person killed in the game. For example, with n=10, k=2, the 1st person to get killed is the 2nd. How can I get this answer? Is there anyway I can find it using the algorithm above?

josephus c
1 Answers

An O(m*lg(km)) algorithm

n people in a ring, numbered from 0 to n-1 clockwise. Start from person with number 0, every m-th is executed, the following program give number of the k-th killed person. k start from 0.

def solve(n,m,k):
    if m==1: return k
    i = (k+1)*m-1
    while i>=n:
        i = (m*(i-n))//(m-1)
    return i

Explanation

I use // to denote floor divison.

let's say everyone will additionally count off from 0, who reports m-1 is the 0-th killed person. who reports 2m-1 is the 1-th killed person and so on.

Say somebody reports i. His last reports is j. When he reports j, there are j//m dead, n-(j//m) alive.

So i = (n - (j//m)) + j -> j-j//m = i-n

Suppose j = am + b; 0<=b<m-1; a,b is int, notice here b!=m-1 because he won't die.

Then a(m-1) + b = (i-n) . Using bezout's lemma and extended euclidean algorithm, we got a=-c; b=(i-n)+c*(m-1); with any int c. And b has only one solution in interval [0,m-1). So b = ((i-n)+c*(m-1)) %(m-1), which equals to (i-n)%(m-1). After that, you can calculate j=(i-n) + (i-n)//(m-1) = (m*(i-n))//(m-1).

By this recurrence relation, you can calculate any k-th killed person.

Time complexity O(m*lg(mk)).

An O(n*lg(n)) simulation algorithm

If m is pretty large, you can use some Balance Tree to implement an O(n*lg(n)) algorithm.

# pip install sortedcontainers
from sortedcontainers import SortedList
def simulate(n, m):
    # all index start from 0
    people = SortedList(range(n))
    idx = 0
    while len(people)>0:
        idx = (idx+m-1)%len(people)
        yield people.pop(idx) # yield executed people number in order
    return
user_77215250
Related