Home Cooking XML Page Civil War Letters Art

# 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.