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.

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, and these techniques are not suitable with uLisp on an Arduino. Fortunately there are non-recursive procedures, which generate the permutations one at a time [3].

The program

First we define a function swp that swaps items i and j of a list:

(defun swp (lst i j)
  (let ((tmp (nth i lst)))
    (setf (nth i lst) (nth j lst))
    (setf (nth j lst) tmp)))

Here's the function rin that calls a function fun with each permutation of the list bel:

(defun rin (fun bel)
  (let ((n (length bel))
        (c (mapcar (lambda (x) 0) bel))
        (o (mapcar (lambda (x) 1) bel))
        j s q)
    (loop
     (setq j (1- n))
     (setq s 0)
     (funcall fun bel)
     (loop
      (setq q (+ (nth j c) (nth j o)))
      (unless (or (= (1- q) j) (< q 0)) (return))
      (when (= j 0) (return))
      (when (= (1- q) j) (incf s))
      (setf (nth j o) (- (nth j o)))
      (decf j)
      (setq q (+ (nth j c) (nth j o))))
      
     (when (= j 0) (return))
     (swp bel (+ (- j (nth j c)) s) (+ (- j q) s))
     (setf (nth j c) q))))

For example, to print the permutations of (1 2 3 4 5) evaluate:

(rin print '(1 2 3 4 5))

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 bel (lis)
  (mapc 
   (lambda (x) (note 9 x 4) (delay 500) (note) (delay 125))
   lis)
  (delay 500))

For example, to play one sequence of descending notes in the scale of C:

(bel '(7 5 4 2 0))

and to ring the changes of all 120 permutations:

(rin bel '(7 5 4 2 0))

This takes about 8 minutes!


  1. ^ Permutations using recursion on Lispology.
  2. ^ Permutations using recursion 2 on Lispology.
  3. ^ Knuth, Donald (2011), "Section 7.2.1.2: Generating All Permutations", The Art of Computer Programming, volume 4A.