[r-t] Change ringing mentioned in "The Art of Computer Programming" Vol. 4A

Simon Gay Simon.Gay at glasgow.ac.uk
Mon Dec 19 16:31:03 UTC 2011

Sorry if this is already well-known, but I have only just discovered it.

Volume 4A of "The Art of Computer Programming" by Donald Knuth,
published this year, contains a reference to change ringing. "Plain
changes" is presented as an algorithm for generating all permutations of
n objects.

For those who are not familiar with "The Art of Computer Programming",
it is an epic series of books on algorithms, begun in the 1960s and
envisaged as 7 chapters, each of which became a large volume. Volume 4A
has just been published and in principle should be followed by volumes
4B, 4C etc and maybe even 5, 6 and 7. (But Knuth is getting quite old...)

A few years ago, Knuth started releasing drafts of Volume 4 for
comments, so the relevant section of Volume 4A can be found here:


and actually dates back to at least 2004.

I have a copy of the published Volume 4A on my desk at the moment
(believe it or not, I was trying to look up something work-related...),
and the relevant text is essentially the same as in the preprint
version, although I think the quote from Duckworth on page iii has been

The highlights are on pages iii, 1, 4, 5, 21, 31.

Actually, the whole of Volume 4A is about combinatorial searching, so
it's quite possible that it contains material that might be relevant to
composition searching.


The University of Glasgow, charity number SC004401

More information about the ringing-theory mailing list