de Bruijn Sequences

Suppose we have an alphabet of size k. Consider all the strings of length n using the symbols in that alphabet. So if k is 2 and n is 3, that would be:

          000
          001
          010
          011
          100
          101
          110
          111
        

A de Bruijn sequence is a circular arrangement so that each of those sequences appears only once. For example, for our k=2, n=3 example one such sequence is:

01110001

We get 011 at position 1, then 111 at position 2, and so on, through 110, 100, 100, 000, and 001, wrapping around back to the front to end with 010, and finally 101. All of the possibilities, only once. It follows that a de Bruijn sequence of order n over an alphabet of size k will be of length pow(k,n) and that every rotation of this sequence or its reversal is also a de Bruijn sequence.

The algorithm for constructing a de Bruijn sequence is relatively straight-forward recursive algorithm. The wikipedia page gives the algorithm due to Frank Ruskey, which produces the lexicographically lowest of the possible sequences.

Since I do most of my work in XQuery, which is a pure functional language, the implementation requires a little adjustment, because I can't just set values in a global array. I use a sparse array implemented with a map.

declare %private function this:ruskey(
  $a as map(*),        (: a: sparse array data structure :)
  $k as xs:integer,    (: k: size of alphabet :)
  $n as xs:integer,    (: n: length of sequences :)
  $t as xs:integer,    (: t: current index into array, starting at 1 :)
  $p as xs:integer,    (: p: combinatorial index, starting at 1 :)
  $ones as xs:integer  (: ones: counter, starting at 0 :)
) as map(*)            (: return the updated sparse array :)
{
  if ($ones <= $n) then (
    if ($t > $n) then (
      if ($n mod $p = 0) then (
        $a=>map:put("seq", (
          $a=>map:get("seq"),
          for $j in 1 to $p return $a=>sparse:get($j + 1)
        ))
      ) else $a
    ) else (
      let $a := $a=>sparse:put($t + 1, $a=>sparse:get($t - $p + 1))
      let $a :=
        if ($a=>sparse:get($t + 1) > 0)
        then this:ruskey($a, $k, $n, $t + 1, $p, $ones + 1)
        else this:ruskey($a, $k, $n, $t + 1, $p, $ones)
      return
        fold-left($a=>sparse:get($t - $p + 1) + 1 to $k - 1, $a,
          function($a as map(*), $j as xs:integer) as map(*) {
            let $a := $a=>sparse:put($t + 1, $j)
            return this:ruskey($a, $k, $n, $t + 1, $t, $ones + 1)
          }
        )
    )
  ) else (
    $a
  )
};
          

Using de Bruijn Sequences for Art

de Bruijn sequences can be used to provide a patterning that looks somewhat random and somewhat regular: a nice artistic balance. Here is an example where the sequence is used for colouring of the tiles.

A colour palette is created by sampling a good number N of colours for the number of divisions in the grid. Each tile has two colours chosen from this palette. To choose the colours, a binary de Bruijn sequence is generated with enough 2 log₂(N) bits. As we march through the rows and columns of the grid, we march through the sequence, taking the first N bits to index into the colour palette for the first colour, and the last N bits to index into the colour palette for the second. This gives us interesting alternations simply.

In this example, each row is a different (random) variation of a 4-bit sequence. The first bit determines whether the inner circle is filled or not; the last bit determines whether there is an outer circle or not, and the middle bits are combined with the first and last bits to make colour choices for the inner and outer circles.