Binary permutations in Lisp

In the book The Elements of Rhythm Volume I rhythms are made using binary strings of N bits, where each bit or binary digit represents one of two values (0 and 1). This means there are 2 possible combinations in 1 bit, 4 combinations in 2 bits and so on.

2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
2⁶ = 64
2⁷ = 128
2⁸ = 256

What follows is my attempt to generate all binary permutations of a given length in Lisp. I know there’s at least one function in the dash library for working with permutations, but it won’t work with binary strings where the elements repeat. In other words, we need to ensure that each element in the list is unique. To do this we create an index of the pattern and transform not the binary but the indexed sequence, which we revert later to its binary equivalent.

To begin we create a set of binary patterns of N elements. The first pattern begins with zeros, then ones are added incrementally to all subsequent patterns.

(defun pattern-create (bits)
  (let (seq (list (make-list bits 0)))
    (while (< (car (last list)) 1)
      (push (setq list (butlast (cl-list* 1 list)))
            seq))
    (append (list (make-list bits 0))
            (nreverse seq))))
;; => ((0 0 0) (1 0 0) (1 1 0) (1 1 1))

Then we rotate the pattern until all possible combinations are exhausted.

(defun pattern-rotate (pattern)
  (let* (patterns
         (map (--map-indexed (cons it-index it) pattern))
         (index (mapcar #'car map)))
    (dolist (permutations (-permutations index))
      (push (mapcar (lambda (idx)
                      (assoc-default idx map))
                    permutations)
            patterns))
    (cl-remove-duplicates patterns :test #'equal)))
;; => ((1 0 0) (0 1 0) (0 0 1))

Finally we iterate the functions to generate all possible combinations of N bits:

(defun patterns (bits)
  (let (patterns)
    (dolist (i (pattern-create bits))
      (let ((permutation (nreverse (pattern-rotate i))))
        (setq patterns (append patterns permutation))))
    patterns))
;; => ((0 0 0) (1 0 0) (0 1 0) (0 0 1)...

So far the results are not sorted sequentially (0001, 0010, 0011, 0100 etc.) where the rightmost digits start over and the next digit is incremented. This is easy to do, although I think shifting the pattern to the right: 1000, 0100, 0010, 0001 etc. would be the most systematic in terms of how rhythm exercises are usually organised. Either way this works well for the purpose of the book as far as I can tell, but the indexing process is expensive and slows things down as the bits increase.

Another approach is to convert integers to base-2 strings using bitwise operations. Here’s a refactored version of this function to make the conversions.

(defun integer-to-binary (integer)
  (let (list)
    (while (> integer 0)
      (setq list (append (list (if (= 1 (logand integer 1))
                                   1 0))
                         (when list list)))
      (setq integer (lsh integer -1)))
    list))

And here’s another one using arithmetic operations.

(defun integer-to-binary (integer)
  (cl-do ((integer integer (floor integer 2))
          (list nil (cons (mod integer 2) list)))
      ((zerop integer) list)))

Finally we create a list of all binary combinations of a given length.

(defun patterns (bits)
  (let (list)
    (dotimes (i (expt 2 bits))
      (let ((binary (integer-to-binary i)))
        (push (append (make-list (- bits (length binary)) 0)
                      binary)
              list)))
    (nreverse list)))
;; => ((0 0 0 0) (0 0 0 1) (0 0 1 0) (0 0 1 1) (0 1 0 0)...

This method is a lot faster compared to my first attempt, and works well for the purpose of the book. Of course, the same can be done in R, Python and possibly most other programming languages as well:

R -e "expand.grid(0:1, 0:1, 0:1, 0:1)"

Still, it’s always a lot more fun to think through these problems yourself, especially when you begin to realise that 1 + 1 is actually 10!

Reply by email
Other posts