De Bruijn sequence


In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring. Such a sequence is denoted by and has length, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of, must start at a different position, because substrings starting at the same position are not distinct. Therefore, must have at least symbols. And since has exactly symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once.
The number of distinct de Bruijn sequences is
For a binary alphabet this is, leading to the following sequence for positive : 1, 1, 2, 16, 2048, 67108864...
The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946. As he later wrote, the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by. The generalization to larger alphabets is due to. Automata for recognizing these sequences are denoted as de Bruijn automata.
In many applications, A =.

History

The earliest known example of a de Bruijn sequence comes from Sanskrit prosody where, since the work of Pingala, each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic yamātārājabhānasalagām is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as Charles Philip Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by Pāṇini".
In 1894, A. de Rivière raised the question in an issue of the French problem journal L'Intermédiaire des Mathématiciens, of the existence of a circular arrangement of zeroes and ones of size that contains all binary sequences of length. The problem was solved, along with the count of distinct solutions, by Camille Flye Sainte-Marie in the same year. This was largely forgotten, and proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well known.
Karl Popper independently describes these objects in his The Logic of Scientific Discovery, calling them "shortest random-like sequences".

Examples

  • Taking A =, there are two distinct B: 00010111 and 11101000, one being the reverse or negation of the other.
  • Two of the 16 possible B in the same alphabet are 0000100110101111 and 0000111101100101.
  • Two of the 2048 possible B in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.

    Construction

The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols.
An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n.
An inverse Burrows–Wheeler transform can be used to generate the required Lyndon words in lexicographic order.
de Bruijn sequences can also be constructed using shift registers or via finite fields.

Example using de Bruijn graph

Goal: to construct a B de Bruijn sequence of length 24 = 16 using Eulerian 3-D de Bruijn graph cycle.
Each edge in this 3-dimensional de Bruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge. If one traverses the edge labeled 1 from 000, one arrives at 001, thereby indicating the presence of the subsequence 0001 in the de Bruijn sequence. To traverse each edge exactly once is to use each of the 16 four-digit sequences exactly once.
For example, suppose we follow the following Eulerian path through these vertices:
These are the output sequences of length k:
This corresponds to the following de Bruijn sequence:
The eight vertices appear in the sequence in the following way:
1 1 1 1 0 1 1 0 0 1 0 1
0 1 1 1 0 1 1 0 0 1 0 1
0 0 1 1 0 1 1 0 0 1 0 1
0 0 0 1 0 1 1 0 0 1 0 1
0 0 0 0 0 1 1 0 0 1 0 1
0 0 0 0 1 1 1 0 0 1 0 1
0 0 0 0 1 1 1 0 0 1 0 1
0 0 0 0 1 1 1 0 0 1 0 1
0 0 0 0 1 1 1 1 0 1 0 1
0 0 0 0 1 1 1 1 0 1 0 1
0 0 0 0 1 1 1 1 0 1 0 1
0 0 0 0 1 1 1 1 0 1 1 1
0 0 0 0 1 1 1 1 0 1 1 0
01 0 1...
... 0 00 1...
... 0 0 01...
...and then we return to the starting point. Each of the eight 3-digit sequences appears exactly twice, and each of the sixteen 4-digit sequences appears exactly once.

Example using inverse Burrows—Wheeler transform

Mathematically, an inverse Burrows—Wheeler transform on a word generates a multi-set of equivalence classes consisting of strings and their rotations. These equivalence classes of strings each contain a Lyndon word as a unique minimum element, so the inverse Burrows—Wheeler transform can be considered to generate a set of Lyndon words. It can be shown that if we perform the inverse Burrows—Wheeler transform on a word consisting of the size-k alphabet repeated kn−1 times, then the result will be the set of all Lyndon words whose length divides n. It follows that arranging these Lyndon words in lexicographic order will yield a de Bruijn sequence B, and that this will be the first de Bruijn sequence in lexicographic order. The following method can be used to perform the inverse Burrows—Wheeler transform, using its standard permutation:
  1. Sort the characters in the string, yielding a new string
  2. Position the string above the string, and map each letter's position in to its position in while preserving order. This process defines the .
  3. Write this permutation in cycle notation with the smallest position in each cycle first, and the cycles sorted in increasing order.
  4. For each cycle, replace each number with the corresponding letter from string in that position.
  5. Each cycle has now become a Lyndon word, and they are arranged in lexicographic order, so dropping the parentheses yields the first de Bruijn sequence.
For example, to construct the smallest B de Bruijn sequence of length 24 = 16, repeat the alphabet 8 times yielding. Sort the characters in, yielding. Position above as shown, and map each element in to the corresponding element in by drawing a line. Number the columns as shown so we can read the cycles of the permutation:
Starting from the left, the Standard Permutation notation cycles are:.
Then, replacing each number by the corresponding letter in from that column yields:.
These are all of the Lyndon words whose length divides 4, in lexicographic order, so dropping the parentheses gives.

Algorithm

The following Python code calculates a de Bruijn sequence, given k and n, based on an algorithm from Frank Ruskey's Combinatorial Generation.

from typing import Iterable, Any
def de_bruijn -> str:
"""de Bruijn sequence for alphabet k
and subsequences of length n.
"""
# Two kinds of alphabet input: an integer expands
# to a list of integers as the alphabet..
if isinstance:
alphabet = list
else:
# While any sort of list becomes used as it is
alphabet = k
k = len
a = * k * n
sequence =
def db:
if t > n:
if n % p 0:
sequence.extend
else:
a = a
db
for j in range:
a = j
db
db
return "".join
print
print

which prints
00010111
aabacadbbcbdccdd
Note that these sequences are understood to "wrap around" in a cycle. For example, the first sequence contains 110 and 100 in this fashion.

Uses

de Bruijn cycles are of general use in neuroscience and psychology experiments that examine the effect of stimulus order upon neural systems, and can be specially crafted for use with functional magnetic resonance imaging.

Angle detection

The symbols of a de Bruijn sequence written around a circular object can be used to identify its angle by examining the n consecutive symbols facing a fixed point. This angle-encoding problem is known as the "rotating drum problem". Gray codes can be used as similar rotary positional encoding mechanisms, a method commonly found in rotary encoders.

Finding least- or most-significant set bit in a word

A de Bruijn sequence can be used to quickly find the index of the least significant set bit or the most significant set bit in a word using bitwise operations and multiplication. The following example uses a de Bruijn sequence to determine the index of the least significant set bit in a 32 bit unsigned integer:

uint8_t lowestBitIndex

The lowestBitIndex function returns the index of the least-significant set bit in v, or zero if v has no set bits. The constant 0x077CB531U in the expression is the B  sequence 0000 0111 0111 1100 1011 0101 0011 0001. The operation zeros all bits except the least-significant bit set, resulting in a new value which is a power of 2. This power of 2 is multiplied by the de Bruijn sequence, thus producing a 32-bit product in which the bit sequence of the 5 MSBs is unique for each power of 2. The 5 MSBs are shifted into the LSB positions to produce a hash code in the range , which is then used as an index into hash table BitPositionLookup. The selected hash table value is the bit index of the least significant set bit in v.
The following example determines the index of the most significant bit set in a 32 bit unsigned integer:

uint32_t keepHighestBit
uint8_t highestBitIndex

In the above example an alternative de Bruijn sequence is used, with corresponding reordering of array values. The choice of this particular de Bruijn sequence is arbitrary, but the hash table values must be ordered to match the chosen de Bruijn sequence. The keepHighestBit function zeros all bits except the most-significant set bit, resulting in a value which is a power of 2, which is then processed as in the previous example.