Ringing the changes

#1

Here’s a program that uses the new setf function in uLisp Version 1.3 to produce all the n! (n factorial) permutations of the n items in a list:

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

(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 all the permutations of (1 2 3 4) evaluate:

(rin print '(1 2 3 4))

Ringing every permutation of church bells is a popular exercise with bell-ringers, called ringing the changes. Here’s a routine to play a complete 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:

(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!

Another application would be a doorbell that plays a different sequence of chimes every time it is pressed.