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 an Arduino Mega 2560 or similar board.
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 , 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:
(next '(2 1 3 4 5))
(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:
(next '(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.
First we define a function find that finds the first item in a list lst that's greater than x:
(defun find (x lst) (cond ((null lst) nil) ((< x (car lst)) (car lst)) (t (find x (cdr lst)))))
> (find 3 '(1 2 4 5 6)) 4
Next we define substitute that replaces every occurrence of an item old with the item new in a list lst:
(defun substitute (new old lst) (cond ((null lst) nil) ((eq old (car lst)) (cons new (substitute new old (cdr lst)))) (t (cons (car lst) (substitute new old (cdr lst))))))
> (substitute 2 3 '(1 3 4 5)) (1 2 4 5)
Finally, here's the definition of next, following the recursive definition given above:
(defun next (lst) (cond ((not (apply > (cdr lst))) (cons (car lst) (next (cdr lst)))) ((> (car lst) (cadr lst)) nil) (t (let* ((rest (reverse (cdr lst))) (old (find (car lst) rest))) (cons old (substitute (car lst) old rest))))))
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 (function lst) (when lst (funcall function lst) (all function (next lst))))
> (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 9 and GND on an Arduino Mega 2560:
(defun bell (lis) (mapc (lambda (x) (note 9 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 7))
Now we can ring the changes of all 120 permutations of these notes:
(all bell '(0 2 4 5 7))
This takes about 8 minutes!
Here's the whole program: Ringing the changes program.