Stack Overflow
Stack Overflow

Questions tagged [josephus]

In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game

Quoting the corresponding wikipedia page:

There are 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. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

71 questions
25
votes
2 answers

Explanation for recursive implementation of Josephus problem

EDIT: n is the number of persons. k is the kth person being eliminated. So for k=2, every 2nd person is getting eliminated. int josephus(int n, int k) { if (n == 1) return 1; else return (josephus(n - 1, k) + k-1) % n + 1; } The code is as…
rents
  • 768
  • 1
  • 7
  • 22
17
votes
1 answer

Hard to understand Haskell memory allocation behaviour

I stumbled upon Haskell and FP and got stunned by the possibilities. And the old maths nerd inside me had no trouble writing naive code for actual useful purposes. However inspite of all the reading I still really have a hard time understanding how…
Mathias Dolidon
  • 3,775
  • 1
  • 20
  • 28
14
votes
8 answers

Removal of every 'kth' person from a circle. Find the last remaining person

As part of a recent job application I was asked to code a solution to this problem. Given, n = number of people standing in a circle. k = number of people to count over each time Each person is given a unique (incrementing) id. Starting with the…
Ash
  • 60,973
  • 31
  • 151
  • 169
14
votes
5 answers

Josephus sequence

Description: There are 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…
CDT
  • 10,165
  • 18
  • 66
  • 97
12
votes
1 answer

Josephus for large n (Facebook Hacker Cup)

Last week I participated in round 1b of the Facebook Hacker cup. One of the problems was basically the Josephus problem I've studied the Josephus problem before as a discrete math problem, so I basically understand how to get the recurrence: f(n,k)…
Edward Tonai
  • 121
  • 1
  • 5
11
votes
4 answers

Looping over numbers

So this is the question that is given. You are in a room with a circle of 100 chairs. The chairs are numbered sequentially from 1 to 100. At some point in time, the person in chair #1 will be asked to leave. The person in chair #2 will be skipped,…
user2677350
  • 338
  • 2
  • 13
11
votes
1 answer

How come these Python codes perform so much differently

Please look at the following code to solve the same set of problem, I do not think that mentioning the problem would anyhow help the purpose, it's yet another iteration of the Josephus problem: Solution 1: import sys from math import log cases=…
whizzzkid
  • 1,174
  • 12
  • 30
9
votes
8 answers

"Josephus-p‌r‌o‌b‌l‌e‌m" using list in python

I wanted to know if it will be possible to solve the Josepheus problem using list in python. In simple terms Josephus problem is all about finding a position in a circular arrangement which would be safe if executions were handled out using a skip…
user904976
7
votes
4 answers

Take every k-th element from the (1 .. n) natural numbers series

For example, we have series 1, 2, 3, 4, 5. We take every 3 element => 3, 1, 5, 2, 4 (chosen element shouldn't remain, we can take while series is not empty). Naive implementation by circle doubly linked list is not good idea cause of performance.…
Evgeniy
  • 171
  • 3
  • 9
5
votes
1 answer

How to prove this josephus problem variation is a np-complete problem?

I have a problem that is a Josephus problem variation. It is described below: There are m cards with number from 1 to m，and each of them has a unique number. The cards are dispatched to n person who sit in a circle. Note that m >= n. Then we choose…
Xudong Chen
  • 53
  • 5
4
votes
3 answers

Calculating Josephus Permutations efficiently in Javascript

While training in code-wars I came across a challenge about Joseph-permutations, I tried solving it on paper first and latter translate it to code. The problem is as follows: "Create a function that returns a Josephus permutation, taking as…
ISTTeo
  • 41
  • 3
4
votes
1 answer

About Josephus_problem

I am trying to solve the Josephus problem, and I have working code. def J(n,x): li=range(1,n+1) k = -1 while li: print li k = (k+x) % len(li) li.pop(k) k =k- 1 J(10, 3) Now I want rewrite it to get the…
chyanog
  • 599
  • 5
  • 14
3
votes
1 answer

How to solve Josephus Elimination using Circular linked list

class Node { public int Data { get; set; } public Node Next { get; set; } public int Counter { get; set; } public Node(int element,int counter) { Data = element; …
Desire
  • 563
  • 4
  • 13
  • 28
3
votes
2 answers

Josephus Permutation (Removal Order) in O(n.logn)

Is there a way to print out the order of removal in the Josephus problem in O(n.logn) ? Example With number of people is n = 7 and number of skip k = 3. The order of elimination would be: 3, 6, 2, 7, 5, 1, 4
unglinh279
  • 675
  • 4
  • 24
3
votes
2 answers

Recurrence relation in Josephus p‌r‌o‌b‌l‌e‌m

The josephus problem can be solved by the below recursion: josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1 josephus(1, k) = 1 How this recurrence relation has been derived?
Green goblin
  • 9,898
  • 13
  • 71
  • 100
1
2 3 4 5