We define the Josephus problem as follows. Suppose that $n$ people form a circle and that we are given a positive integer $m \le n$. Beginning with a designated first person, we proceed around the circle, removing every $m$th person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all $n$ people. The order in which the people are removed from the circle defines the $(n,m)$-Josephus permutation of integers $1, 2, \ldots, n$. For example, the $(7, 3)$-Josephus permutation is $\langle 3, 6, 2, 7, 5, 1, 4 \rangle$.
- Suppose that $m$ is a constant. Describe an $\O(n)$-time algorithm that, given an integer $n$, outputs the $(n, m)$-Josephus permutation.
- Suppose that $m$ is not a constant. Describe an $\O(n \lg n)$-time algorithm that, given all integers $n$ and $m$, outputs the $(n, m)$-Josephus permutation.
This is a very evil way to spell "an $\O(mn)$-time algorithm". I honestly got stuck here, until I realized that the point was to have a simpler algorithm that does not take $m$ into account.
Thus, it's simple:
- Put all the numbers in a linked list and make it circular
- Start with the first number and loop until you empty the list
- Output the current number, remove it from the list, an advance $m$ times.
At some point you end up removing the last number, which means we're done. It's not that hard to implement, so I would not bother.
$\O(n \lg n)$ time
First of all, we need to use an order statistic tree. Then, we simply start with selecting the $m$-th element, output it, delete it, and then look $m$ elements ahead, wrapping around with some modulo arithmetic and accounting for the deleted element.
Python code below. Note that the index awkwardness is due to the 1-based
indexing of our ranks. Note as well that we don't just need
also the size property of the tree/root.
import sys, os sys.path.append(os.path.join(os.path.dirname(__file__), '..', 'misc')) from order_statistic_tree import OrderStatisticTree def josephus(n, m): tree = OrderStatisticTree() for i in list(range(1, n + 1)): tree.insert(i) current = 1 result =  while tree.root: current = (current + m - 2) % tree.root.size + 1 node = tree.select(current) result.append(node.key) tree.delete(node.key) return tuple(result)