
de Bruijn SequencesSuppose we have an alphabet of size 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 01110001 We get The algorithm for constructing a de Bruijn sequence is relatively straightforward 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 foldleft($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 Artde 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 In this example, each row is a different (random) variation of a 4bit 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. 