Order of elimination in Josephus p‌r‌o‌b‌l‌e‌m

Question

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

People are standing in a circle waiting to be executed. Counting begins at the first point in the circle and proceeds around the circle in a clockwise direction. After a specified number of people are skipped, the next person is 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 remains, and is freed. For example if n=10 then the order of elimination is 2, 4, 6, 8, 10, 3, 7, 1, 9 and 5

The problem is, without simulation of the above game, try to find out the order of 
elimination through means of mathematical formula or a mathematical pattern.

Initially we are given n i.e the number of people in the circle at the start. Give the order of elimination keeping in mind the above conditions and constraints.

In simple words, print the pattern of deaths without using any data structures like arrays and linked lists.

Answer 1

I have prepared the solution after studying http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf . This recursive is mentioned in the above pdf.

int last_man(int n,int x)
{
    if(n==1 && x==1)
        return 1;
    else if(n>1 && x==1)
        return 2;
    else if(last_man(n-1,x-1)==n-1)
        return 1;
    else
        return last_man(n-1,x-1)+2;
}

X denotes the xth person to die and n is the total number of people initially. Looping this function over all values of x from 1 to n gives us the order of elemination.

Answer 2

function josIterative(n, k) {
let queue = [];
for (let i = 1; i <= n; i++) queue.push(i);

let deathOrder = [];

while (queue.length !== 1) {
    for (let skip = 1; skip < k; skip++) queue.push(queue.shift());
    deathOrder.push(queue.shift());
}

console.log("Death order is " + deathOrder.join(" "));
return queue[0]; //survivor
}

console.log(josIterative(7, 3) + " is survivor");

This program is written in javascript es6. Queue takes care to preserve the new position Alternate way is to solve using recurrence relation

Answer 3

There's an approach that uses ordered set

(https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/):

• Initialize an ordered set V, and insert the elements in the range [1, N] into V.
• Initialize a variable, say pos as 0, to store the index of the removed element.
• Iterate until the size of V is greater than 1, and perform the following steps:
  • Store the size of the set in a variable, say X
  • Update the value of pos to (pos + K) % X
  • Print the element pointed by pos in V and then erase it
  • Update pos to pos%V.size()
• Print the last element stored at the beginning of set V

Here's the code:

#include <iostream>
using namespace std;

// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set                          \
    tree<int, null_type, less<int>, rb_tree_tag, \
        tree_order_statistics_node_update>

// Function to find the person who
// will get killed in the i'th step
void orderOfExecution(int N, int K)
{

    // Create an ordered set
    ordered_set V;

    // Push elements in the range
    // [1, N] in the set
    for (int i = 1; i <= N; ++i)
        V.insert(i);

    // Stores the position to be removed
    int pos = 0;

    // Iterate until the size of the set
    // is greater than 1
    while (V.size() > 1) {

        // Update the position
        pos = (pos + K) % (int)V.size();

        // Print the removed element
        cout << *(V.find_by_order(pos)) << ' ';

        // Erase it from the ordered set
        V.erase(*(V.find_by_order(pos)));

        // Update position
        pos %= (int)V.size();
    }

    // Print the first element of the set
    cout << *(V.find_by_order(0));
}

int main()
{
    int N = 5, K = 2;

    // Function Call
    orderOfExecution(N, K);

    return 0;
}

Time Complexity: O(N * log(N))

For better understanding, I recommend checking out this video:

https://youtu.be/KnsDFCcBJbY