Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a k-ary De Bruijn sequenceB(k, n) of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn
Nicolaas Govert de Bruijn
Nicolaas Govert de Bruijn is a Dutch mathematician, affiliated as professor emeritus with the Eindhoven University of Technology. He received his Ph.D. in 1943 from Vrije Universiteit Amsterdam....
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
A with size k for which every possible subsequence
Subsequence
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements...
of length n in A appears as a sequence of consecutive characters exactly once.
Each B(k, n) has length kn.
There are distinct De Bruijn sequences B(k, n).
According to De Bruijn himself, 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 Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest
Tatyana Pavlovna Ehrenfest
Tatyana Pavlovna Ehrenfest, later van Aardenne-Ehrenfest, was a Dutch mathematician. She was the daughter of Paul Ehrenfest and Tatyana Alexeyevna Afanasyeva .Tatyana Ehrenfest was born in Vienna, and spent her childhood in St Petersburg...
and himself.
History
The earliest known example of the De Bruijn sequence comes in Sanskrit
Sanskrit
Sanskrit , is a historical Indo-Aryan language and the primary liturgical language of Hinduism, Jainism and Buddhism.Buddhism: besides Pali, see Buddhist Hybrid Sanskrit Today, it is listed as one of the 22 scheduled languages of India and is an official language of the state of Uttarakhand...
In linguistics, prosody is the rhythm, stress, and intonation of speech. Prosody may reflect various features of the speaker or the utterance: the emotional state of the speaker; the form of the utterance ; the presence of irony or sarcasm; emphasis, contrast, and focus; or other elements of...
. The mnemonic yamātārājabhānasalagā was invented by Sanskrit
Sanskrit
Sanskrit , is a historical Indo-Aryan language and the primary liturgical language of Hinduism, Jainism and Buddhism.Buddhism: besides Pali, see Buddhist Hybrid Sanskrit Today, it is listed as one of the 22 scheduled languages of India and is an official language of the state of Uttarakhand...
prosodists to memorize the names of three-letter patterns as per the naming convention for three-letter sequences of long and short letters in Pingala
Pingala
Pingala is the traditional name of the author of the ' , the earliest known Sanskrit treatise on prosody.Nothing is known about Piṅgala himself...
Year 200 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Maximus and Cotta...
). Denoting a long letter as L and short as S, this mnemonic corresponds to the sequence SLLLSLSSSL. By allowing wrapping around, the last two letters can be dropped from the mnemonic to give the circular mnemonic yamātārājabhānasa. The corresponding sequence is SLLLSLSS which is a B(2, 3) sequence for A = {S, L}.
Though the name De Bruijn is attached to these sequences due to his proof of K. Posthumus' conjecture in 1946, in 1975 he acknowledged that priority in this proof belonged to C. Flye Sainte-Marie, who had independently published it in 1894 after the question had been raised in print by A. de Riviere that same year. De Bruijn notes that the problem was also examined in 1934 and again independently in 1944.
The Logic of Scientific Discovery is a 1934 book by Karl Popper. It was originally written in German and titled Logik der Forschung. Then Popper reformulated his book in English and republished it in 1959. This forms the rare case of a major work to appear in two languages, both written and one...
, calling them "shortest random-like sequences".
Examples
Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse and/or negation of the other.
Two of the 2048 possible B(2, 5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.
Construction
The De Bruijn sequences can be constructed by taking a Hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...
over k symbols (or equivalently, a Eulerian cycle of a (n − 1)-dimensional De Bruijn graph), or via finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s.
An alternative construction involves concatenating together, in lexicographic order, all the Lyndon word
Lyndon word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
s whose length divides n.
Example
Goal: to construct a B(2, 4) De Bruijn sequence of length 24 = 16 using Eulerian (n − 1 = 4 − 1 = 3) 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 nodes:
000, 000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101, 010, 100, 000.
These are the output sequences of length k:
0 0 0 0
_ 0 0 0 1
_ _ 0 0 1 1
This corresponds to the following De Bruijn sequence:
0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1
The eight vertices appear in the sequence in the following way:
...and then we return to the starting point. Each of the eight 3-digit sequences (corresponding to the eight vertices) appears exactly twice, and each of the sixteen 4-digit sequences (corresponding to the 16 edges) appears exactly once.
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
code calculates a De Bruijn sequence, given k and n, based on an algorithm from Frank Ruskey
Frank Ruskey
Frank Ruskey is a combinatorialist and computer scientist, and professor at the University of Victoria. His research involves algorithms for exhaustively listing discrete structures, combinatorial Gray codes, Venn and Euler diagrams, combinatorics on words, and enumerative combinatorics...
's Combinatorial Generation.
def de_bruijn(k, n):
"""De Bruijn Sequence for alphabet size k
and subsequences of length n."""
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p 0:
for j in range(1, p + 1): sequence.append(a[j])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1,1)
return sequence
print(de_bruijn(2, 3))
which prints
[0, 0, 0, 1, 0, 1, 1, 1]
Uses
The sequence can be used to shorten a brute-force attack on a PIN
Personal identification number
A personal identification number is a secret numeric password shared between a user and a system that can be used to authenticate the user to the system. Typically, the user is required to provide a non-confidential user identifier or token and a confidential PIN to gain access to the system...
-like code lock that does not have an "enter" key and accepts the last n digits entered. For example, a digital door lock with a 4-digit code would have B(10, 4) solutions, with length . Therefore, only at most (as the solutions are cyclic) presses are needed to open the lock. Trying all codes separately would require presses.
The symbols of a De Bruijn sequence written around a circular object (such as a wheel of a robot
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
In geometry, an angle is the figure formed by two rays sharing a common endpoint, called the vertex of the angle.Angles are usually presumed to be in a Euclidean plane with the circle taken for standard with regard to direction. In fact, an angle is frequently viewed as a measure of an circular arc...
by examining the n consecutive symbols facing a fixed point. Gray code
Gray code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code....
s can be used as similar rotary positional encoding mechanisms.
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
Functional magnetic resonance imaging
Functional magnetic resonance imaging or functional MRI is a type of specialized MRI scan used to measure the hemodynamic response related to neural activity in the brain or spinal cord of humans or other animals. It is one of the most recently developed forms of neuroimaging...
.
A De Bruijn sequence can be used to quickly find the first or last bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
right|thumb|A De Bruijn torus. Each 2-by-2 binary matrix can be found within it exactly once.In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet that contains every m-by-n matrix exactly once...
is a toroidal array with the property that every k-ary m-by-n matrix occurs exactly once. (It is not necessary that the array be expressed toroidally; the array can be mapped into a 2-dimensional array. Because it is toroidal it "wraps around" on all 4 sides.)
Such a pattern can be used for two-dimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the m-by-n matrix directly adjacent to the sensor, and calculating its position on the De Bruijn torus.
De Bruijn decoding
Computing the position of a particular unique tuple or matrix in a De Bruijn sequence or torus is known as the De Bruijn Decoding Problem. Efficient decoding algorithms exists for special, recursively constructed sequences and extend to the two dimensional case. De Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.
External links
