14-2 Josephus permutation

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 the integers $1, 2, \ldots, n$. For example, the $(7, 3)$-Josephus permutation is $\langle 3, 6, 2, 7, 5, 1, 4 \rangle$.

a. Suppose that $m$ is a constant. Describe an $O(n)$-time algorithm that, given an integer $n$, outputs the $(n, m)$-Josephus permutation.

b. Suppose that $m$ is not a constant. Describe an $O(n\lg n)$-time algorithm that, given integers $n$ and $m$, outputs the $(n, m)$-Josephus permutation.

(Removed)