# Problem 14.2

# Josephus permutation

We define the

Josephus problemas 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 permutationof 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.

## Constant $m$

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

Easy-peasy.

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 `OS-SELECT`

, but
also the size property of the tree/root.

### Python code

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)