robert@cheviot.UUCP (Robert Stroud) (12/18/84)
In net.lang.c, Larry Wall (lwall@sdcrdcf.UUCP) asks whether John Lipinski's permutation algorithm (lip@masscomp.UUCP) has anything to do with change ringing... > It looks suspiciously like a change ringing > algorithm. Can any of you ... Angles across the water confirm it? > For those of you who haven't heard of change ringing, it is an artform > practiced by the British in which a set of tuned bells is rung through > all possible permutations. As a practising campanologist (or bellringer) I am qualified to answer this question and shed some light on these arcane matters. First of all, we do not ring "through all possible permutations". If we did, it would take us a very long time. Bells which are "hung for ringing" usually come in sets (or "rings") of anything from 4 to 12 bells, although more (or less) are quite possible. If we reckon that it takes about a minute to ring 24 permutations (or "changes") then we have the following: Bells Permutations Time 4 24 1 minute 5 120 5 minutes 6 720 30 minutes 7 5,040 3 hours 30 minutes 8 40,320 1 day 4 hours 12 479,001,600 37 years 355 days It is very common to ring about 5000 changes (a "peal") and typically this takes about 3 hours depending on the weight of the bells. However, longer peals have been rung - the longest being all possible permutations of 8 bells (a "full extent"), i.e. 40,320 changes which were rung in slightly less than 24 hours (I don't have the exact figure to hand) for the first time in July 1963. This was a remarkable achievement; there was no "cheating" - 8 people stood in a belfry and pulled bell ropes for the best part of a day without stopping. It is unlikely ever to be surpassed and certainly nobody is contemplating ringing all possible permutations on 12 bells (the neighbours would complain :-)!) As for whether the program is a change-ringing program, I am afraid the answer is no. We are very choosy about the order in which we ring our changes. In particular, there are rules of symmetry and regularity which must be obeyed - the 40,320 changes were generated using only 5 permutation operators (in a mathematical sense) with severe restrictions on when they could be used. It is obviously important to be systematic if you are trying to ring a lot of changes; it is also important to be musical. One of the criteria for judging music is that the bells should be kept moving as much as possible. This rules out the method of enumerating permutations used by the algorithm, which fixes all but the last so many bells and recursively generates all permutations of the remaining bells. On the other hand, bells cannot move more than one position at a time because this would be physically impossible to ring (when you have a large bell weighing several tons on the end of a rope you don't argue with it - you let it ring at its speed!). To illustrate some of these concepts, here is the output from the permutation program for four bells (24 changes), and what a bell-ringer would call "Plain Bob Minimus". Read down each column, left to right, (i.e. I piped the output through "pr -3"!). First the permutation program, 1234 1423 3412 2134 4123 4312 1324 4213 4231 3124 2413 2431 3214 1432 4321 2314 4132 3421 1243 1342 3241 2143 3142 2341 Now for Plain Bob Minimus (generated by hand!) 1234 1342 1423 2143 3124 4132 2413 3214 4312 4231 2341 3421 4321 2431 3241 3412 4213 2314 3142 4123 2134 1324 1432 1243 ---- ---- ---- 1342 1423 1234 (head of the next column) Each column (or "lead") is constructed using an identical series of permutation operators. In fact only the half lead is constructed; the second half of each lead is a mirror image of the first half, (i.e. the same operators are applied in reverse order). The link from the end of one column to the start of a new column is achieved with a different permutation operator which has the effect of shuffling the bells round a bit to prevent repetition. Notice how the 1 which corresponds to the lightest bell (or "treble") does the same thing in each lead (it is called a "hunt" bell). The other bells do something different in each lead but when viewed cyclically they all do exactly the same "work" - they just start at different points in the cycle. For example, at the end of the first lead the 2 is in thirds place so it does in the second lead what the 3 did in the first lead. The cycle is also symmetrical - you only have to learn half of it, then you do what you just did in reverse! Some light will be shed on all this if you draw a "blue-line" through the path of a particular bell. This is what bell-ringers learn, not the complete list of permutations nor the list of operators (which we call "place-notation"). The place-notation for Plain Bob Minimus is X.14.X.14 12 where X means "exchange every pair of bells" and 14 means "keep the bells in positions 1 and 4 in the same place and exchange all the other pairs". The "12" by itself is what happens at the end of the lead to start the next lead. I should explain that when I say "Plain Bob Minimus" I mean the "method" (very loosely, something constructed like this) "Plain Bob" as rung on four bells ("Minimus"). I have given a "plain-course" of Bob Minimus above which is all you can ring without repeating yourself using the rules I have given, but is also all there is to ring on 4 bells. In general, a plain course of Plain Bob on N bells has 2*N*(N-1) changes which is nowhere near N factorial. To get all the changes (or at least more) two new permutation operators called "Bob" and "Single" are introduced which may be applied manually at a lead-end instead of the usual 12 operator. In practice, there is someone called a "Conductor" who is responsible for shouting Bob or Single at appropriate moments (only at lead ends), thereby causing the normal sequence of leads to be interrupted. The peal of 40,320 changes I referred to earlier was actually a full extent of "Plain Bob Major" whose place notation is X.18.X.18.X.18.X.18 12 with Bob=14 and Single=1234 I leave the generation of the 40,320 changes according to these rules as an exercise for my readers (:-) Needless to say, I have only scratched the surface of what to me is a very fascinating subject. If anyone else out there is interested, I will be happy to answer any queries about bell-ringing by mail (except that I will be away for Christmas soon). Perhaps if there is enough interest we could start a news group...!! Robert J Stroud, University of Newcastle upon Tyne (UUCP) ...!ukc!cheviot!robert (ARPA) robert%cheviot%newcastle.mailnet@mit-multics.arpa (JANET) robert@newcastle.cheviot.janet
jaw@ames.UUCP (James A. Woods) (12/29/84)
# Note: The following tintinnalogical offering should be read whilst humming
# Pete Seeger's "The Bells of Rhymney" (1964) in the key of control-G.
We laud our very own campanologist Robert Stroud (ukc!cheviot!robert)
for his commentary on change-ringing. His account certainly rings true;
I only wish to add a reference to the lore, to be found in the
December 1977 issue of ACM Computing Surveys.
In his fascinating addendum to Robert Sedgewick's classic
exposition "Permutation generation methods" (appearing in the same journal,
June 1977), a Mr. I. R. MacCallum of the Dept. of Computer Science,
Univ. of Essex at Colchester, chimes in to discuss the following bits
of ephemera:
(a) the roots of the Johnson/Trotter algorithm (1962) in the early
years of the 17th century, as reported in the collaborative effort
of Stedman/Duckworth in 1688 ("Tintinnalogia", also avail. as
a Kingsmead Reprint, Bath, 1970).
(b) the complex definition of "peals" and "extents" provided by the
Central Council of Church Bell Ringers, with applicability
to the playing of Grandsire Triples, a particularly harmonious
composition of 5,040 (7!) changes. MacCallum, incidently, offers
Algol 60 code for a Grandsire peal composed by John Vicars of Oxford
to the interested reader.
(c) accounts of 8-bell extents (40,320 changes), the only "true"
performance (i.e. verified by independent umpires) being achieved
by the Leicester Diocesan Guild at the Bell Foundry, Loughborough
on Saturday July 27th, 1963, in 17 hours 58 1/2 minutes.
Ah, the stuff of Guinness Book! I consider it right up there
with Sedgewick's three-instruction permutation generator inner loop.
Since campanologists may not resort to "visible aids to memory in
conducting or ringing", the fine (read "appealing") art practiced by
Mr. Stroud is algorithmic, indeed.
-- James A. Woods {hplabs,ihnp4,vortex}!ames!jaw (jaw@riacs.ARPA)
P.S.
This writer, also, is eagerly awaiting the Macintosh multi-voice
rendering of Plain Bob Major for his "wallpaper music" collection.
Perhaps bessel(3M) functions would serve as the appropriate inharmonic
sound envelope, with menu bars for Tibetan, Big Ben, and Liberty bell
variants. Next stop -- a Phillip Glass machine!
P.P.S.
I hope net.audio and net.music.folk are listening in on this...