Josephus Problem: Classic elimination puzzle solved with linked lists.
The Josephus problem is a famous theoretical problem dating back to ancient times. It asks: if n people stand in a circle and every k-th person is eliminated, which position survives? This problem has fascinated mathematicians for centuries and demonstrates elegant algorithmic solutions.
Historical Context
The Legend
Named after Flavius Josephus, a Jewish historian who, according to legend, used this strategy to save himself and a friend from capture during the Siege of Yodfat (67 CE). The problem has been studied for centuries and appears in many mathematical contexts.
Mathematical Significance
The Josephus problem is:
- Historically important: One of the oldest algorithmic problems
- Mathematically interesting: Has closed-form solutions
- Algorithmically elegant: Demonstrates circular data structures
- Recursively solvable: Can be solved with recurrence relations
Problem Statement
Setup
Given n people numbered 1 to n arranged in a circle:
- Start counting from person 1
- Count k people clockwise
- Eliminate the k-th person
- Continue counting from the next person
- Repeat until only one person remains
Question
What is the position of the survivor?
Example: n=7, k=3
Round 1: [1, 2, 3, 4, 5, 6, 7]
Count: 1→2→3, eliminate 3
Remaining: [1, 2, 4, 5, 6, 7]
Round 2: [1, 2, 4, 5, 6, 7]
Count: 4→5→6, eliminate 6
Remaining: [1, 2, 4, 5, 7]
Round 3: [1, 2, 4, 5, 7]
Count: 7→1→2, eliminate 2
Remaining: [1, 4, 5, 7]
... continue until one remains
Algorithm
Implementation Strategy
This implementation uses DynDlist (doubly-linked list) to simulate the elimination process, and manually wraps the iterator to the first element when it reaches the end (to model the circle):
josephus(n, k):
1. Create list with persons 1 to n
2. current = first person
3. While list.
size() > 1:
a. Advance iterator k-1 positions (skip k-1 people)
b. Remove person at current position
c. Continue from
next person (circular wrap-around)
4. Return remaining person
size_t size(Node *root) noexcept
void next()
Advance all underlying iterators (bounds-checked).
Why a List + Wrap-around Iterator?
- Natural fit: Problem is inherently circular
- Efficient removal: O(1) removal at the iterator position
- Wrap-around: Implemented by resetting the iterator to the first element
- Simple: Easy to implement and understand
Time Complexity
Approaches
| Approach | Time Complexity | Notes |
| Naive simulation | O(n × k) | Simulate each elimination |
| Circular list | O(n × k) | But efficient in practice |
| Recurrence relation | O(n) | Mathematical solution |
| Closed form | O(1) | Formula-based (complex) |
This Implementation
- Time: O(n × k) - n eliminations, k steps each
- Space: O(n) - store n people
- Practical: Efficient for reasonable n and k
Mathematical Solution
Recurrence Relation
The Josephus problem has a recurrence relation:
J(n, k) = (J(n-1, k) + k) mod n
J(1, k) = 0
Where J(n, k) is the 0-indexed position of the survivor.
Closed-Form Formula
For k=2, there's a closed-form solution:
__gmp_expr< T, __gmp_unary_expr< __gmp_expr< T, U >, __gmp_log2_function > > log2(const __gmp_expr< T, U > &expr)
__gmp_expr< T, __gmp_unary_expr< __gmp_expr< T, U >, __gmp_floor_function > > floor(const __gmp_expr< T, U > &expr)
For general k, the formula is more complex.
Applications
Algorithm Design
- Circular data structures: Demonstrates circular lists
- Elimination algorithms: Pattern for elimination problems
- Recursive thinking: Shows recursive problem structure
Game Theory
- Elimination games: Model elimination tournaments
- Strategies: Analyze optimal strategies
- Fairness: Study fairness of elimination processes
Cryptography
- Encryption schemes: Some schemes use similar patterns
- Key generation: Generate keys using elimination patterns
Resource Allocation
- Round-robin elimination: Allocate resources fairly
- Process scheduling: Schedule processes in rounds
- Load balancing: Distribute load in circular fashion
Real-World Examples
- Musical chairs: Children's game
- Elimination tournaments: Sports tournaments
- Survivor shows: TV show elimination format
Example Walkthrough
n=7, k=3 (Detailed)
Initial: [1, 2, 3, 4, 5, 6, 7]
Round 1: Count 1→2→3, eliminate 3
[1, 2, 4, 5, 6, 7]
Round 2: Count 4→5→6, eliminate 6
[1, 2, 4, 5, 7]
Round 3: Count 7→1→2, eliminate 2
[1, 4, 5, 7]
Round 4: Count 4→5→7, eliminate 7
[1, 4, 5]
Round 5: Count 1→4→5, eliminate 5
[1, 4]
Round 6: Count 1→4→1, eliminate 1
[4]
Survivor: Position 4
Usage
# 7 people, eliminate every 3rd
joseph -n 7 -p 3
# Classic problem: 41 people, every 3rd eliminated
joseph -n 41 -p 3
# Different elimination step
joseph -n 10 -p 5
Special Cases
k=1
- Trivial: Eliminate sequentially
- Survivor: Last person (position n)
k=2
- Special case: Has closed-form solution
- Pattern: Survivor position follows pattern
k ≥ n
- Wrap-around: Counting wraps around circle
- Equivalent: k mod n
Extensions
Variations
- Reverse counting: Count counter-clockwise
- Skip pattern: Variable skip count
- Multiple survivors: Keep k survivors instead of 1
- Different starting: Start from different position
- See also
- tpl_dynDlist.H Circular doubly-linked list implementation
-
linear_structures_example.C List structures (related)
- Author
- Leandro Rabindranath León
Definition in file joseph.C.
1.9.8