## Flavius Josephus

### February 19, 2009

A simple solution just counts through a list of the living moving the head of the list to the end of the list until the current list element must die, when it is moved from the living list to the deceased list:

```(define (josephus1 n m)   (let loop ((k m) (alive (range 0 n)) (dead '()))     (cond ((null? (cdr alive)) (reverse (cons (car alive) dead)))           ((= k 1) (loop m (cdr alive) (cons (car alive) dead)))           (else (loop (- k 1) (append (cdr alive) (list (car alive))) dead)))))```

That works, but in quadratic time due to the append operation, which must repeatedly trace down the living list. We can fix that by using the old trick of representing a queue as two lists, front and back, consing new items to the head of back, and replacing front with the reverse of back whenever front is exhausted:

```(define (josephus2 n m)   (let loop ((k m) (front (range 0 n)) (back '()) (dead '()))     (cond ((and (null? front) (null? back)) (reverse dead))           ((null? front) (loop k (reverse back) '() dead))           ((= k 1) (loop m (cdr front) back (cons (car front) dead)))           (else (loop (- k 1) (cdr front) (cons (car front) back) dead)))))```

Another linear solution is to create a list and set the last element of the list to point back to the first, forming a circle. Then just count around the circle, extracting the requested element at each iteration, each time reforming the list, until the tail of the list points to itself.

```(define (cycle xs)   (set-cdr! (last-pair xs) xs) xs)```

```(define (josephus3 n m)   (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))     (cond ((= (car alive) (cadr alive))             (reverse (cons (car alive) dead)))           ((= k 1)             (let ((dead (cons (cadr alive) dead)))               (set-cdr! alive (cddr alive))               (loop (- m 1) (cdr alive) dead)))```

Josephus survived in 31st position, counting from one.

```> (josephus 41 3) (2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30)```

This code can be executed at http://programmingpraxis.codepad.org/RMwrace2.

Pages: 1 2

### 18 Responses to “Flavius Josephus”

1. Sasha B said

Depending on your interpretation of “every third person”, this question could be done a few different ways.

```def josephus(n, m):
"""Returns a list of n people, numbered from 0 to n - 1,
in the order in which they are executed (every mth person
in turn). The sole surviver is the last person in the list.
>>> josephus(40, 3) # Kill every 3rd person
"""

people = range(n)
current = m - 1
executions = []
while len(people) > 1:
executions.append(people.pop(current))
current += m - 1 # Advance m people
current = current % len(people) # In case we go past the first person
return executions + [people[0]]
```
2. […] For the correct Haskell solution check the first comment on the challenge page. […]

3. kawas said

I’ve tried two clojure versions : one using modulus, filtering “alive” vector and an other using the trick of the front and back queue.
Both functions have the same size but the second one is clearly an order of magnitude faster.
Seems like modulus and filtering entire vector are expensive compared to only playing with head, tail and last element of front & back vectors :)

```(defn josephus [n m]
(loop [idx m front (range n) back [] dead []]
(cond
(and (empty? front) (empty? back)) dead
(empty? front) (recur idx back [] dead)
(= idx 1) (recur m (next front) back (conj dead (first front)))
:else (recur (dec idx) (next front) (conj back (first front)) dead))))

(josephus 41 3)
```
4. Alex said

My solution using C
void josephus ( int n, int m)
{
int i, j, kill = m – 1;
int reset = 0;
int circle[n], killOrder[n];

for (i = 0; i < n; i++)
circle[i] = i;

for ( i = 0; i < n; i++)
{
killOrder[i] = kill;
circle[kill] = -1;
for ( j = 0; j n – 1)
{
kill = 0;
}
while (circle[kill] == -1)
kill++;
}

}

for (i = 0; i < n; i++)
printf("%d\t%d \n", i, killOrder[i]);

}

5. Alex said

Ok i fail at posting. Not sure how to do the code block thingy. Copy pasting lost some of my code.

6. Alex said

OK.. sorry about the triple post… I read the HOWTO post source code section.

And here is my solution using C:

http://pastebin.com/T08Jpj7G

7. My variant using Python lambda’s and list slices:

http://pastebin.com/pVgE9hF2

8. Yuri said

Scheme solution that makes use of circular lists:
http://pastebin.com/faTX0j6q

9. j0sejuan said

golang

```package main

import (
"fmt"
"container/ring"
)

func josephus(N, k int) {
r := ring.New(N)
for n := 0; n < N; n++ {
r.Value = n
r.Next()
}
for r.Len() > 1 {
fmt.Printf("%d killed\n", r.Value.(int))
r.Move(k)
}
}

func main() {
josephus(41, 3)
}
```
10. kevin galkov said

in coffeescript:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 murder = (howMany, bounce) -> people = [0..howMany] # people from 0 to 40 for i in people people[i] = 1 killed = Array() count=0 for i in [1..howMany] whichOne = i*bounce – howMany*count count++ if whichOne> (howMany-bounce) if people[whichOne] is 1 killed.push whichOne people[whichOne] = 0; for i in [0..howMany] if people[i] is 1 then console.log i output = "" for i in killed output += i+", " console.log output console.log "not killed:" console.log killed[howMany-1] murder(41,3)

view raw

gistfile1.txt

hosted with ❤ by GitHub

11. […] is another one taken from Programming Praxis #5 – Flavius Josephus, has a historical background which can be found here. For this exercise, write a function that […]

12. Eleanore said

She said thewy often see people at seo keyword research tool the worst point in their careers.
”In the UK we already have the tension and pressure seo
keyword research tool they can collect. The online programs in psychology seo keyword research
tool to teach it! The parents of teenagers under the age of 80 Baroness Bakewell better
known as broadcaster Joan Bakewell faces a fight much closer to home.
Skye is not interested in the issue of same-sex attraction than my male patients.

13. Christophe said

Solution using Clojure. Very slow, but correct.

```(defn rotate
[n coll]
(let [c (count coll)]
(take c (drop (mod n c) (cycle coll)))))

(defn execute
(if (< (count ps) m)
(let [executed (nth ps (dec m))
alive    (take (dec m) ps)
rest     (drop m ps)
newalive (rotate (dec m) (concat alive rest))
(execute m newalive newdead (dec limit)))))

(defn josephus
[n m]
(let [people (range 0 n)]
(execute m people '())))

```
14. Bill Wood said

Rust version

```/*  Author Bill Wood
Order N
"killed" people are tracked using a vec, where each entry contains the index of
the next "living" person, and is updated to bypass each person who is "killed"
*/
struct Josephus {
people: Vec<usize>,
m: usize,
current: usize,
count: usize,
}

impl Iterator for Josephus {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
if self.count == 0 {
return None
}
let mut prev = self.current;
for _i in 0..self.m {
prev = self.current;
self.current = self.people[self.current];
}
self.count -= 1;
self.people[prev] = self.people[self.current];
Some(self.current)
}
}

impl Josephus {
fn new(size: usize, m: usize) -> Self {
let mut j = Josephus{ count: size, m: m, current: size - 1, people: vec!() };
for i in 0..size - 1 {
j.people.push(i + 1);
}
j.people.push(0);
j
}
}

fn main() {
let mut x = Josephus::new(41, 3).peekable();
while let Some(p) = x.next() {
if x.peek().is_none() {
println!("\nfinal position = {}", p)
} else {
print!("{} ", p);
}
}
}
```
15. matthew said

If we are doing old problems, here’s a neat recursive solution in Python (not the most efficient being n^2, we can use a similar trick to find the final position in linear time though).

```def josephus(m,k):
if m == 1: return [0]
else: return [k-1] + [(k+i)%m for i in josephus(m-1,k)]

print(josephus(41,3))

# [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0,
#  4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33,
#  39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 34, 30]
```
16. matthew said

Oops, should have checked that more carefully (note repeated 34 in “solution” there). I hope this is right:

```def josephus(m,k):
if m == 1: return [0]
else: return [(k-1)%m] + [(k+i)%m for i in josephus(m-1,k)]
```

We should be able to define a similar but more complex recurrence that takes a complete trip around the remaining circle at each step.