91/04/21 < C O P Y >
To: Dr. Michael W. Ecker
REC, 909 Violet Terrace, Clarks Summit, PA 18411
From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070
Enclosure: MS-DOS disk (Josephus).
Dear Mike,
There are so many interesting challenges in the Jan/Feb/Mar 1991
issue of REC that I don't know where to begin. I have started
working on several of them, but have been concentrating on "The
Thousand Roman Slaves" problem suggested by Steve Wagler. This is,
as you noted, actually a classic known as the Josephus problem.
Original Problem: 1000 slaves in a circle, numbered 1 to 1000, are
all to be shot except one lucky survivor. The order of shooting is
1, 3, 5, etc., always alternating, and always immediately removing
the fallen bodies. Once a body has fallen, it is no longer
considered part of the circle for purposes of future counting and
alternation. Example, n=6: Shoot 1,3,5,2,6; 4 survives.
The General Problem: There is an ordered set of n objects arranged
in a circle with object i (1 <= i <= n) in position i. All n
objects are selected and removed in a certain order and placed in
a new circle with the new position number k beings the order of
selection. Object f is selected first. After each selection, m
minus 1 of the remaining objects following the one removed are
skipped and the next object is then selected. We are interested in
the nature of the permutation generated by this process, its fixed
elements, and in particular the original position L of the last
object selected. Note that m and f can be as low as 1 and can be
larger than n.
A fast way to solve the original problem is to consider the general
problem when m = 2 and f = 1. If n is a power of 2, m = 2 and
f = 1, then object n will be the last one selected. First we remove
all numbers not divisible by 2. Next remove all not divisible by
2 squared. Eventually only n and n/2 is left and it is n/2's time
to get shot. The next step is to realize that when m = 2, if we add
1 to n we will add 2 to L the number of the object that will be
selected last. This leads us to the equation: The last object
selected L = 2^P - 2(2^P - n) = 2n - 2^P, where 2^P is the next
power of 2 greater than or equal to n. For n = 1000 the last object
selected L = 1024 - 48 = 2000 - 1024 = 976.
The equation L = 2n - 2^P and the statements above can be verified
by using the equation given by Prof. Donald E. Knuth in his book
The Art of Computer Programming, Vol. 1, Pages 181, problem 31.
Knuth always selects object m first, so f = m instead of 1. The
result of his equation has to be adjusted by subtracting m - f and
corrected by +/-n if out of the range [1, n].
Knuth refers to this as the Flavius Josephus problem in his Index
and Glossary. He also has a reference to this problem in Vol. 3 of
this set of books. His equation states that the k'th man to be
executed, for general m and n, is in position x which may be
computed as follows: Set x = km, then repeatedly set
x = Int((m(x - n) - 1) / (m - 1))
until x <= n. The x <= n test needs to be done before the first
application of the equation.
I have included a disk containing 5 programs, Joseph1.Pas through
Joseph5.Pas. All allow the operator to specify n, m, f; and
computes L. The Program Joseph1 uses the mod function to speed up
the solution. This is important when m is large compared to the
number of objects r remaining in the circle. The Pascal statement:
for i:= 1 to ((m-1) mod r) do ...
is used to skip over the next m-1 objects, but actually only skips
over (m-1) mod r objects. This improvement was not in Knuth's MIX
program *JOSEPHUS PROBLEM on pg 516 of Vol. 1.
It is important to consider situations when m is very large, at
least as large as (n - 1)!. There are n! different permutations
that can be made of an ordered set of n distinct objects. The first
object can be selected in n ways the second in n - 1 ways etc. If
we consider the general problem with n = 4, we can generate all 24
permutations by allowing m to range from 1 to 6 and allowing f to
range from 1 to 4. When n = 5 we cannot generate all 120
permutations, only 60, but m must be allowed to be as large as 12
to do this.
Here is a sample output from Joseph1 with n = 8, m = 4, f = 4:
Execution order, when object i was selected:
5 4 6 1 3 8 7 2
Order of execution, object # selected on k'th selection:
4 8 5 2 1 3 7 6
The resulting permutation expressed in cyclic notation:
(1, 5, 3, 6, 8, 2, 4)(7)
n = 8, m = 4, f = 4: Object 6 was selected last!
There is 1 fixed element: 7.
The execution order shows that 1 was executed 5th, 2 was executed
4th, etc. The order of execution shows that 4 was executed 1st, 8
was 2nd, etc. The permutation expressed in cyclic notation shows
that 1 was moved to position 5, 5 moved to 3, 3 to 6, 6 to 8, 8 to
2, 2 to 4, 4 to 1 and 7 was picked 7th. Seven is the only fixed
element of the permutation.
Joseph2 uses Knuth's equation given above to solve the problem.
Knuth did not suggest that this would make an efficient program,
and it is much slower than Joseph1. It is given as a verification
that Joseph1 is producing correct results.
Joseph3 searches for Josephus permutations with many fixed
elements. Here is a sample output:
n = 25, m = 25, f = 1: 9 last! 6 fixed: 1, 2, 8, 13, 14, 23.
n = 59, m = 33, f = 22: 14 last! 7 fixed: 9, 15, 19, 26, 28,
45, 58.
n = 90, m = 42, f = 50: 90 last! 8 fixed: 2, 16, 23, 51, 58,
61, 69, 90.
n = 232, m = 189, f = 88: 114 last! 9 fixed: 3, 39, 64, 85,
112, 133, 159, 165, 206.
n = 1000, m = 54, f = 965: 694 last! 8 fixed: 39, 355, 435,
541, 558, 708, 807, 996.
Joseph4 is a graphical solution of the Josephus problem. It shows
a display with the n points arranged in a circle. Starting from
point 1, each point has a directed line segment drawn from it to
the next point to be selected.
Joseph5 shows Graphical Orbits in Josephus permutations. It again
shows a display with the n points arranged in a circle. Each point
i has a directed line segment drawn from its original position i
to its new position k resulting from the permutation. This is the
most fun program of the set. Start it with n = 1, m = 1, f = 1; and
repeatedly press the + on the key pad. The program will progress
through various values of the three variables.
Sincerely,
Harry
times since October 20, 2004.