Massive Algorithms: Josephus problem

Josephus problem

Video: https://www.youtube.com/watch?v=fZ3p2Iw-O2I

Josephus problem | Set 1 (A O(n) Solution) - GeeksforGeeks
There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The problem has following recursive structure.

  josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
  josephus(1, k) = 1

After the first person (kth from begining) is killed, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons. But the position returned by josephus(n – 1, k) will consider the position starting from k%n + 1. So, we must make adjustments to the position returned by josephus(n – 1, k).

Recursive Version: Time Complexity: O(n)

int josephus(int n, int k)

{

  if (n == 1)

    return 1;

  else

    /* The position returned by josephus(n - 1, k) is adjusted because the

       recursive call josephus(n - 1, k) considers the original position 

       k%n + 1 as position 1 */

    return (josephus(n - 1, k) + k-1) % n + 1;

}

https://www.cnblogs.com/EdwardLiu/p/6189007.html

Let

f(n, k) = ((f(n-1, k) + k - 1) mod n) + 1,

f(1, k) = 1

这样理解：

新数组len = n-1，其中1th num在原数组的位置是 (k mod n)+1, 也就是 (1 + (k-1))mod n+ 1

2nd num 在原数组位置是（2 + （k-1））mod n + 1

3rd num 在原数组位置是（3 + （k-1））mod n + 1

Following is simple recursive implementation of the Josephus problem. The implementation simply follows the recursive structure mentioned above.

Simulation

13     public int survive(ListNode head, int k) {
14         if (head == null) return -1;
15         ListNode prev = head;
16         while (prev!=null && prev.next!=head) {
17             prev = prev.next;
18         }
19         if (prev == null) return -1; //not a loop
20         //now prev is the previous node of head
21         int count = 1;
22         while (head.next != head) {
23             if (count == k) {
24                 prev.next = head.next;
25                 head = head.next;
26                 count = 1;
27             }
28             else {
29                 head = head.next;
30                 prev = prev.next;
31                 count++;
32             }
33         }
34         return head.val;
35     }

https://medium.com/@rrfd/explaining-the-josephus-algorithm-11d0c02e7212
https://stackoverflow.com/questions/31657262/josephus-algorithm/31657630#31657630

After the first person (kth from begining) is killed, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons.

But the position returned by josephus(n – 1, k) will consider it again from the position 1. So we add k-1 to it and take its modulus with n as there are n elements and add 1 to make the position 1-indexed rather than 0-indexed.

http://en.wikipedia.org/wiki/Josephus_problem

Theorem: If

n=2^m+l

and

0\leq l<2^m

, then

f(n) = 2l+1

Proof: We use strong induction on

n

. The base case

n=1

is true. We consider separately the cases when

n

is even and when

n

is odd.

n

is even, then choose

l_1

and

m_1

such that

n/2 = 2^{m_1}+l_1

and

0\leq l_1 < 2^{m_1}

. Note that

l_1 = l/2

. We have

f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1

, where the second equality follows from the induction hypothesis.

n

is odd, then choose

l_1

and

m_1

such that

(n-1)/2 = 2^{m_1}+l_1

and

0\leq l_1 < 2^{m_1}

. Note that

l_1 = (l-1)/2

. We have

f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1

, where the second equality follows from the induction hypothesis. This completes the proof.

We can solve for

l

to get an explicit expression for

f(n)

f(n) = 2(n-2^{\lfloor \log_2(n) \rfloor})+1

The most elegant form of the answer involves the binary representation of size

n

f(n)

can be obtained by a one-bit left cyclic shift of

n

itself. If we represent

n

in binary as

n=1 b_1 b_2 b_3\dots b_m

, then the solution is given by

f(n)=b_1 b_2 b_3 \dots b_m 1

. The proof of this follows from the representation of

n

2^m+l

or from the above expression for

f(n)

We can solve for

l

to get an explicit expression for

f(n)

f(n) = 2(n-2^{\lfloor \log_2(n) \rfloor})+1

The most elegant form of the answer involves the binary representation of size

n

f(n)

can be obtained by a one-bit left cyclic shift of

n

itself. If we represent

n

in binary as

n=1 b_1 b_2 b_3\dots b_m

, then the solution is given by

f(n)=b_1 b_2 b_3 \dots b_m 1

. The proof of this follows from the representation of

n

2^m+l

or from the above expression for

f(n)

Implementation: A simple python function can be:

  def josephus_2( n ):
    from math import log
    return 2*(n - 2**(int(log(n,2))))+1

The general case

The position of the survivor in the remaining circle would be

f(n-1,k)

if we start counting at

1

; shifting this to account for the fact that we're starting at

(k\bmod n)+1

yields the recurrence

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,

which takes the simpler form

g(n,k)=(g(n-1,k)+k) \bmod n,\text{ with }g(1,k)=0

if we number the positions from

0

n-1

instead.

Implementation: A simple python function can be (but might be slow/fail for large n and small k):

  def josephus(n, k):
    if n ==1:
      return 1
    else:
      return ((josephus(n-1,k)+k-1) % n)+1

Alternatively a simple loop can also be run like:

  def josephus(n, k):
    r = 0
    i = 1
    while i <= n:
      r = (r + k) % i;
      i+= 1
    return r+1

http://www.exploringbinary.com/powers-of-two-in-the-josephus-problem/
http://www.codechef.com/OVRN2013/problems/RECRUIT

A New Recruitment Process is being adopted by Software Companies these days. They make the applicants sit in a circle (indexing is 1-based). For a selected value of k, they start counting from the 1st person and eliminate the kth person. Then they start counting from the very next person in the remaining circle and eliminate the 2kth person, and then start again from there and eliminate the 3kth person, until a single applicant remains. That applicant is recruited.

So given the number of applicants n, and for a given value of k, we need to tell them the initial index of the person who got recruited.

http://wenku.baidu.com/view/93767a4d2e3f5727a5e96244.html
http://my.oschina.net/u/247728/blog/70913
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0

现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单：x'=(x+k)%n

∵ k=m%n; 　　

∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n

∴x'= (x+ m%n)%n = (x+m)%n 　　得到 x‘=(x+m)%n

递推公式 f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)

http://qiemengdao.iteye.com/blog/1264485
n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：

scanf("%d%d", &n, &m);
for (i=2; i <=n; i++)
s=(s+m)%i;
printf ("The winner is %d/n", s+1);

Recursive Solution:

int f(int n, int m)
{
if (n > 1)
return (m + f(n - 1, m)) % n;
else
return 0;
}

https://nishantarora.in/the-josephus-problem.naml
Approach 3: Also known as the Josephus Extended Problem, if k=2 and n is very large, the problem can be solved in O(k logn). Wikipedia has the theorem to prove this, the function is just so simple:

from math import log

  def josephus_2( n ):

    return 2*(n - 2**(int(log(n,2))))+1

By emulation:
http://yuanhsh.iteye.com/blog/2229239
Variant:
Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One to One Hundred.

At some point in time, the person in chair #1 will be told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining.. the survivor. Note that the chair is removed when the person leaves the room. Write a program to figure out which chair the survivor is sitting in. Please send us the answer and your working code.

public int findSurvivor() {
int n = 100; // number of chairs
List<Integer> chairs = new LinkedList<>();
for(int i=1; i<=n; i++) {
chairs.add(i);
}
int step = 1;
Iterator<Integer> itr = chairs.iterator();
while (chairs.size() > 1) {
for (int i = 0; i < step; i++) {
if (!itr.hasNext())
itr = chairs.iterator();
itr.next();
}
itr.remove();
step++;
}
return chairs.get(0);
}

public int findSurvivor() {
int n = 100; // number of chairs
List<Integer> chairs = new ArrayList<>();
for(int i=1; i<=n; i++) {
chairs.add(i);
}
int victim = 0; // the index of chair to be removed
int step = 0;
while (chairs.size() > 1) {
chairs.remove(victim);
victim += ++step;
victim %= chairs.size();
}
return chairs.get(0);
}

http://blog.csdn.net/zdqpp/article/details/5497403

int main()
{
int m,n,k;
cin>>k>>m>>n;
int f=(m-1)%n;
cout<<(f+k-1)%n+1<<" ";
for(int i=2;i<=n;i++)
{
int g=(m-1)%(n-i+1);
for(int j=2;j<=i;j++)
{
g=(g+m)%(n-i+j);
}
f=g;
cout<<(f+k-1)%n+1<<" ";
}
cout<<endl;
return 0;
}

http://mayanknatani.wordpress.com/2013/03/17/josephus-problem/
A variant of the problem was asked in codechef recently, You should open the problem and read it first.So as you have read the problem , you might have understood that the above recursion will not work in this case, so we have to modify out recursion as follows:

f(n,k,m) = (f(n-1,k,m+1) + m*k) %n
Base case : f(1,k,m) =0

Now , as we can see that m is the multiplier of k now every time the (m*k)th element will be eliminated and the last remaining element will be the answer.

f(int n,int k,int m)

   if(n==1):

      return 0

   else:

      return (f(n-1,k,m+1) + m*k) %n

http://rosettacode.org/wiki/Josephus_problem#Java

    public static int execute(int n, int k){
        int killIdx = 0;
        ArrayList<Integer> prisoners = new ArrayList<Integer>(n);
        for(int i = 0;i < n;i++){
            prisoners.add(i);
        }
        System.out.println("Prisoners executed in order:");
        while(prisoners.size() > 1){
            killIdx = (killIdx + k - 1) % prisoners.size();
            System.out.print(prisoners.get(killIdx) + " ");
            prisoners.remove(killIdx);
        }
        System.out.println();
        return prisoners.get(0);
    }
 
    public static ArrayList<Integer> executeAllButM(int n, int k, int m){
        int killIdx = 0;
        ArrayList<Integer> prisoners = new ArrayList<Integer>(n);
        for(int i = 0;i < n;i++){
            prisoners.add(i);
        }
        System.out.println("Prisoners executed in order:");
        while(prisoners.size() > m){
            killIdx = (killIdx + k - 1) % prisoners.size();
            System.out.print(prisoners.get(killIdx) + " ");
            prisoners.remove(killIdx);
        }
        System.out.println();
        return prisoners;
    }

Extended Josephus problem
Problem definition: There are n persons, numbered 1 to n, around a circle. We eliminate second of every two remaining persons until one person remains. Given the n, determine the number of xth person who is eliminated
http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf
http://www.cnblogs.com/tractorman/p/4057624.html
　　0，1，...，n-1这n个数排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

　　例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删词第3个数字，则删除的前四个数字一次是2、0、4、1，因此最后剩下的数字是3.

下面利用数学推导，如果能得出一个通式，就可以利用递归、循环等手段解决。下面给出推导的过程：

（1）第一个被删除的数为 (m - 1) % n。

（2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一个简单的映射。

   k -----> 0
   k+1 ------> 1
   k+2 ------> 2
   ...
   ...

k-2 ------> n-2

这是一个n -1个人的问题，如果能从n - 1个人问题的解推出 n 个人问题的解，从而得到一个递推公式，那么问题就解决了。假如我们已经知道了n -1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为 (x + k) % n。其中k等于m % n。代入(x + k) % n <=> (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n

（3）第二个被删除的数为(m - 1) % (n - 1)。

（4）假设第三轮的开始数字为o，那么这n - 2个数构成的约瑟夫环为o, o + 1, o + 2,......o - 3, o - 2.。继续做映射。

   o -----> 0
   o+1 ------> 1
   o+2 ------> 2
   ...
   ...

o-2 ------> n-3

这是一个n - 2个人的问题。假设最后的胜利者为y，那么n -1个人时，胜利者为 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)

要得到n - 1个人问题的解，只需得到n - 2个人问题的解，倒推下去。只有一个人时，胜利者就是编号0。下面给出递推式：

f [1] = 0;
f [ i ] = ( f [i -1] + m) % i; (i>1)

有了递推公式，实现就非常简单了，给出循环的两种实现方式。再次表明用标准库的便捷性。

int JosephusProblem_Solution3(int n, int m)
{
 if(n < 1 || m < 1)
  return -1;

 int *f = new int[n+1];
 f[0] = f[1] = 0;        //f[0]其实用不到的

 for(unsigned i = 2; i <= n; i++)
  f[i] = (f[i-1] + m) % i; //按递推公式进行计算

 int result = f[n];
 delete []f;

 return result;
}

int JosephusProblem_Solution4(int n, int m)
{
 if(n < 1 || m < 1)
  return -1;

 vector<int> f(n+1,0);
 for(unsigned i = 2; i <= n; i++)
  f[i] = (f[i-1] + m) % i;

 return f[n];
}

int LastRemaining(unsigned int n,unsigned int m)
{
    if(n<1 || m<1)
        return -1;

    unsigned int i = 0;
    list<int> nums;
    for(i= 0;i<n;i++)
        nums.push_back(i);
    list<int>::iterator cur = nums.begin();
    while(nums.size()>1)
    {
        for(int i = 1;i<m;i++)
        {
            cur++;
            if(cur==nums.end())
                cur = nums.begin();
        }
        list<int>::iterator next = ++cur;
        if(next == nums.end())
            next = nums.begin();

        --cur;
        nums.erase(cur);
        cur = next;
    }
    return *cur;    
}

https://www.geeksforgeeks.org/josephus-problem-set-2-simple-solution-k-2/

In this post, a special case is discussed when k = 2

Examples :

Input  : n = 5
Output : The person at position 3 survives
Explanation : Firstly, the person at position 2 is killed, 
then at 4, then at 1 is killed. Finally, the person at 
position 5 is killed. So the person at position 3 survives.

Input  : n = 14
Output : The person at position 13 survives

Below are some interesting facts.

In first round all even positioned persons are killed.
For second round two cases arise
1. If n is even : For example n = 8. In first round, first 2 is killed, then 4, then 6, then 8. In second round, we have 1, 3, 5 and 7 in positions 1st, 2nd, 3rd and 4th respectively.
2. If n is odd : For example n = 7. In first round, first 2 is killed, then 4, then 6. In second round, we have 3, 5, 7 in positions 1st, 2nd and 3rd respectively.

If n is even and a person is in position x in current round, then the person was in position 2x – 1 in previous round.

If n is odd and a person is in position x in current round, then the person was in position 2x + 1 in previous round.

From above facts, we can recursively define the formula for finding position of survivor.

Let f(n) be position of survivor for input n, 
the value of f(n) can be recursively written 
as below.

If n is even
   f(n) = 2f(n/2) - 1
Else
   f(n) = 2f((n-1)/2) + 1

Solution of above recurrence is

f(n) = 2(n - 2floor(Log2n) + 1
     = 2n - 21 + floor(Log2n) + 1

    static int josephus(int n) 

    { 

        // Find value of 2 ^ (1 + floor(Log n)) 

        // which is a power of 2 whose value 

        // is just above n. 

        int p = 1; 

        while (p <= n) 

            p *= 2; 

        // Return 2n - 2^(1+floor(Logn)) + 1 

        return (2*n) - p + 1; 

    }

Josephus problem

Labels

Popular Posts