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.

a. We use a circular list in which each element has two attributes, $key$ and $next$. At the beginning, we initialize the list to contain the keys $1, 2, \ldots, n$ in that order. This initialization takes $O(n)$ time, since there is only a constant amount of work per element (i.e., setting its $key$ and its $next$ attributes). We make the list circular by letting the $next$ attribute of the last element point to the first element.

We then start scanning the list from the beginning. We output and then delete every $m$th element, until the list becomes empty. The output sequence is the $(n, m)$-Josephus permutation. This process takes $O(m)$ time per element, for a total time of $O(mn)$. Since m is a constant, we get $O(mn) = O(n)$ time, as required.

b. We can use an order-statistic tree, straight out of Section 14.1. Why? Suppose that we are at a particular spot in the permutation, and let's say that it's the $j$th largest remaining person. Suppose that there are $k \le n$ people remaining. Then we will remove person $j$, decrement $k$ to reflect having removed this person, and then go on to the $(j + m - 1)$ largest remaining person (subtract $1$ because we have just removed the $j$th largest). But that assumes that $j + m \le k$. If not, then we use a little modular arithmetic, as shown below.

In detail, we use an order-statistic tree $T$, and we call the procedures $\text{OS-INSERT}$, $\text{OS-DELETE}$, $\text{OS-RANK}$, and $\text{OS-SELECT}$:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
JOSEPHUS(n, m)
    initialize T to be empty
    for j = 1 to n
        create a node x with x.key == j
        OS-INSERT(T, x)
    k = n
    j = m
    while k > 2
        x = OS-SELECT(T.root, j)
        print x.key
        OS-DELETE(T, x)
        k = k - 1
        j = ((j + m - 2) mod k) + 1
    print OS-SELECT(T.root, 1).key

The above procedure is easier to understand. Here's a streamlined version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
JOSEPHUS(n, m)
    initialize T to be empty
    for j = 1 to n
        create a node x with x.key == j
        OS-INSERT(T, x)
    j = 1
    for k = n downto 1
        j = ((j + m - 2) mod k) + 1
        x = OS-SELECT(T.root, j)
        print x.key
        OS-DELETE(T, x)

Either way, it takes $O(n\lg n)$ time to build up the order-statistic tree $T$, and then we make $O(n)$ calls to the order-statistic-tree procedures, each of which takes $O(\lg n)$ time. Thus, the total time is $O(n\lg n)$.