Ringing the changes
Change ringing, or campanology, is the art of ringing church bells to produce sequences of chimes. For example, if there are five bells the simplest sequence, consisting of ringing the bells in descending order of pitch, could be labelled (1 2 3 4 5), and this is called rounds.
One of the most popular sequences of chimes that bell-ringers have traditionally produced is called plain changes, which goes through every permutation of the bells, sounding each sequence exactly once before returning to the first sequence. An additional constraint of the plain changes sequence is that every step involves exchanging two adjacent bells in the sequence.
This example gives a uLisp program that rings the changes through a piezo speaker connected to a pin on the Arduino. It will run on any platform.
Introduction
With n bells there are n! (factorial) permutations, or n! + 1 if we include the additional repetition of rounds at the end. There are some intuitive recursive techniques to calculate all the permutations of n items [1][2], but generating a full list requires a lot of memory.
I've recently come up with the following fairly intuitive recursive procedure that takes a permutation, as a list of integers, and generates the next permutation, and this requires a lot less memory. So, for example:
(nxt '(2 1 3 4 5))
will give:
(2 1 3 5 4)
The permutations are generated in lexical order; in other words, the order they would be listed in a telephone directory, so if we are generating the permutations of the first five digits, the first permutation will be (1 2 3 4 5) and the last one will be (5 4 3 2 1). Calling:
(nxt '(5 4 3 2 1))
will return nil to indicate that there are no more permutations.
We can express a recursive algorithm to generate the next one from a given permutation, as follows:
- We divide the current permutation into the head element, and the remaining elements.
For example, for (2 1 3 4 5) we get 2 and (1 3 4 5).
- Unless the remaining elements are in descending order, the next permutation is the head element followed by the next permutation of the remaining elements.
So, in this case, the next permutation is 2 followed by the next permutation of (1 3 4 5).
- If the remaining elements are in descending order, we need to change the head element to give the next permutation.
For example, for (2 5 4 3 1) calling next on (5 4 3 1) will return nil, because there's no next permutation. We therefore need to swap the head element, 2, with the next available digit, and follow it by the first permutation of the remaining digits.
First we reverse the order of the remaining digits; because they were originally in descending order they are now in ascending order: in this example (1 3 4 5).
Now we find the first digit in this list that's greater than the head element. In this case it's 3.
Finally we swap this with the head element to give (3 1 2 4 5) as the next permutation.
The program
First we define a function fnd that finds the first item in a list lst that's greater than x:
(defun fnd (x lst) (cond ((null lst) nil) ((< x (car lst)) (car lst)) (t (fnd x (cdr lst)))))
For example:
> (fnd 3 '(1 2 4 5 6)) 4
Next we define sub (substitute) that replaces the first occurrence of an item old with the item new in a list lst:
(defun sub (new old lst) (cond ((null lst) nil) ((eq old (car lst)) (cons new (cdr lst))) (t (cons (car lst) (sub new old (cdr lst))))))
For example:
> (sub 2 3 '(1 3 4 5)) (1 2 4 5)
Finally, here's the definition of nxt, following the recursive definition given above:
(defun nxt (lst) (cond ((not (apply > (cdr lst))) (cons (car lst) (nxt (cdr lst)))) ((> (car lst) (cadr lst)) nil) (t (let* ((rest (reverse (cdr lst))) (old (fnd (car lst) rest))) (cons old (sub (car lst) old rest))))))
For example:
> (nxt '(2 1 3 4 5)) (2 1 3 5 4)
To test it, here's a routine all that repeatedly applies a function to the next permutation of a list until it returns nil:
(defun all (fun lst) (when lst (funcall fun lst) (all fun (nxt lst))))
For example:
> (all print '(1 2 3)) (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1) nil
Playing the bells
Here's a routine to play a sequence of bells using a piezo speaker connected between pin 11 and GND on an Arduino Uno. If you have a piezo speaker with leads spaced 0.3" you can plug it directly between pin 11 and GND on the Arduino header.
(defun bel (lis) (mapc (lambda (x) (note 11 x 4) (delay 500) (note) (delay 125)) lis) (delay 500))
For example, to play one sequence of ascending notes in the scale of C:
(bel '(0 2 4 5))
Now we can ring the changes of all 24 permutations of these notes:
(all bel '(0 2 4 5))
On platforms with a bit more memory, such as the Arduino Mega 2560, you can ring the changes of all 120 permutations of five notes with:
(all bel '(0 2 4 5 7))
This takes about 8 minutes!
Here's the whole program: Ringing the changes program.
- ^ Permutations using recursion on Lispology.
- ^ Permutations using recursion 2 on Lispology.