View source for De Bruijn sequence

{{Short description|Cycle through all length-k sequences}}
{{lowercase}}
[[File:De Bruijn sequence.svg|thumb|The de Bruijn sequence for alphabet size {{nowrap|1= ''k'' = 2}} and substring length {{nowrap|1=  ''n'' = 2}}. In general there are many sequences for a particular ''n'' and ''k'' but in this example it is unique, [[Up to|up to]] cycling.]]

In [[Combinatorics|combinatorial]] [[Mathematics|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 (computer science)#Formal theory|string]] on ''A'' occurs exactly once as a [[Substring|substring]] (i.e., as a ''contiguous'' [[Subsequence|subsequence]]). Such a sequence is denoted by {{nowrap|''B''(''k'', ''n'')}} and has length {{nowrap|''k''<sup>''n''</sup>}}, which is also the number of distinct strings of length ''n'' on ''A''. Each of these distinct strings, when taken as a substring of {{nowrap|''B''(''k'', ''n'')}}, must start at a different position, because substrings starting at the same position are not distinct. Therefore, {{nowrap|''B''(''k'', ''n'')}} must have ''at least'' {{nowrap|''k''<sup>''n''</sup>}} symbols. And since {{nowrap|''B''(''k'', ''n'')}} has ''exactly'' {{nowrap|''k''<sup>''n''</sup>}} 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 {{nowrap|''B''(''k'', ''n'')}} is
:<math>\dfrac{\left(k!\right)^{k^{n-1}}}{k^n}.</math>

The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946.{{sfnp|de Bruijn|1946}} As he later wrote,{{sfnp|de Bruijn|1975}} the existence of de Bruijn sequences for each order together with the above properties were first [[Mathematical proof|proved]], for the case of alphabets with two elements, by {{harvs|first=Camille|last=Flye Sainte-Marie|year=1894|txt}}. The generalization to larger alphabets is due to {{harvs|first1=Tatyana|last1=van Aardenne-Ehrenfest|last2=de Bruijn|year=1951|txt}}. [[Automata theory|Automata]] for recognizing these sequences are denoted as de Bruijn automata.

In most applications, ''A'' = {0,1}.

== 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".<ref>{{harvtxt|Brown|1869}}; {{harvtxt|Stein|1963}}; {{harvtxt|Kak|2000}}; {{harvtxt|Knuth|2006}}; {{harvtxt|Hall|2008}}.</ref>

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 <math>2^n</math> that contains all <math>2^n</math> binary sequences of length <math>n</math>. The problem was solved (in the affirmative), along with the count of <math>2^{2^{n-1} - n}</math> distinct solutions, by Camille Flye Sainte-Marie in the same year.{{sfnp|de Bruijn|1975}} This was largely forgotten, and {{harvtxt|Martin|1934}} 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 [[Conjecture|conjecture]]d the count <math>2^{2^{n-1} - n}</math> for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well-known.{{sfnp|de Bruijn|1975}}

[[Biography:Karl Popper|Karl Popper]] independently describes these objects in his ''The Logic of Scientific Discovery'' (1934), calling them "shortest random-like sequences".{{sfnp|Popper|2002}}

== Examples ==
* Taking ''A'' = {0,&thinsp;1}, there are two distinct ''B''(2,&nbsp;3): 00010111 and 11101000, one being the reverse or negation of the other.
* Two of the 16 possible ''B''(2,&nbsp;4) in the same alphabet are 0000100110101111 and 0000111101100101.
* Two of the 2048 possible ''B''(2,&nbsp;5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.

== Construction ==
[[File:De bruijn graph-for binary sequence of order 4.svg|right|thumb|A de Bruijn graph. Every four-digit sequence occurs exactly once if one traverses every edge exactly once and returns to one's starting point (a Eulerian cycle). Every three-digit sequence occurs exactly once if one visits every vertex exactly once (a Hamiltonian path).]]
The de Bruijn sequences can be constructed by taking a [[Hamiltonian path]] of an ''n''-dimensional [[De Bruijn graph|de Bruijn graph]] over ''k'' symbols (or equivalently, an Eulerian cycle of an (''n''&nbsp;&minus;&nbsp;1)-dimensional de Bruijn graph).{{sfnp|Klein|2013}}

An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides ''n''.<ref>According to {{harvtxt|Berstel|Perrin|2007}}, the sequence generated in this way was first described (with a different generation method) by {{harvtxt|Martin|1934}}, and the connection between it and Lyndon words was observed by {{harvtxt|Fredricksen|Maiorana|1978}}.</ref>

An inverse [[Burrows–Wheeler transform]] can be used to generate the required Lyndon words in lexicographic order.{{sfnp|Higgins|2012}}

de Bruijn sequences can also be constructed using [[Shift register|shift register]]s{{sfnp|Goresky|Klapper|2012}} or via [[Finite field|finite field]]s.{{sfnp|Ralston|1982|pp=136–139}}

===Example using de Bruijn graph===
[[File:de_Bruijn_binary_graph.svg|thumb|300px|Directed graphs of two ''B''(2,3) de Bruijn sequences and a ''B''(2,4) sequence. In ''B''(2,3), each vertex is visited once, whereas in ''B''(2,4), each edge is traversed once.]]

Goal: to construct a ''B''(2,&nbsp;4) de Bruijn sequence of length 2<sup>4</sup> = 16 using Eulerian (''n''&nbsp;−&nbsp;1 = 4&nbsp;−&nbsp;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 vertices:

: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:

       {0  0  0  0} 1  1  1  1  0  1  1  0  0  1  0  1
        0 {0  0  0  1} 1  1  1  0  1  1  0  0  1  0  1
        0  0 {0  0  1  1} 1  1  0  1  1  0  0  1  0  1
        0  0  0 {0  1  1  1} 1  0  1  1  0  0  1  0  1
        0  0  0  0 {1  1  1  1} 0  1  1  0  0  1  0  1
        0  0  0  0  1 {1  1  1  0} 1  1  0  0  1  0  1
        0  0  0  0  1  1 {1  1  0  1} 1  0  0  1  0  1
        0  0  0  0  1  1  1 {1  0  1  1} 0  0  1  0  1
        0  0  0  0  1  1  1  1 {0  1  1  0} 0  1  0  1
        0  0  0  0  1  1  1  1  0 {1  1  0  0} 1  0  1
        0  0  0  0  1  1  1  1  0  1 {1  0  0  1} 0  1
        0  0  0  0  1  1  1  1  0  1  1 {0  0  1  0} 1
        0  0  0  0  1  1  1  1  0  1  1  0 {0  1  0  1}
        0} 0  0  0  1  1  1  1  0  1  1  0  0 {1  0  1 ...
    ... 0  0} 0  0  1  1  1  1  0  1  1  0  0  1 {0  1 ...
    ... 0  0  0} 0  1  1  1  1  0  1  1  0  0  1  0 {1 ...

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

=== Example using inverse Burrows—Wheeler transform ===
Mathematically, an inverse [[Burrows–Wheeler transform|Burrows—Wheeler transform]] on a word {{mvar|w}} generates a multi-set of [[Equivalence class|equivalence class]]es consisting of strings and their rotations.{{sfnp|Higgins|2012}} 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 {{mvar|w}} consisting of the size-''k'' alphabet repeated ''k''<sup>''n''−1</sup> times (so that it will produce a word the same length as the desired de Bruijn sequence), 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''(''k'',''n''), 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'':
# Sort the characters in the string {{mvar|w}}, yielding a new string {{mvar|w{{prime}}}}
# Position the string {{mvar|w{{prime}}}} above the string {{mvar|w}}, and map each letter's position in {{mvar|w{{prime}}}} to its position in {{mvar|w}} while preserving order. This process defines the [http://mathworld.wolfram.com/PermutationCycle.html Standard Permutation].
# Write this permutation in [[Permutation|cycle notation]] with the smallest position in each cycle first, and the cycles sorted in increasing order.
# For each cycle, replace each number with the corresponding letter from string {{mvar|w{{prime}}}} in that position.
# 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''(2,4) de Bruijn sequence of length 2<sup>4</sup> = 16, repeat the alphabet (ab) 8 times yielding {{math|''w''{{=}}abababababababab}}. Sort the characters in {{mvar|w}}, yielding {{math|''w{{prime}}''{{=}}aaaaaaaabbbbbbbb}}. Position {{mvar|w{{prime}}}} above {{mvar|w}} as shown, and map each element in {{mvar|w{{prime}}}} to the corresponding element in {{mvar|w}} by drawing a line. Number the columns as shown so we can read the cycles of the permutation:

[[File:BurrowsWheeler- standard permutation.svg|frameless|630x630px]]

Starting from the left, the Standard Permutation notation cycles are: {{math|(1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16)}}. ([http://mathworld.wolfram.com/PermutationCycle.html Standard Permutation])

Then, replacing each number by the corresponding letter in {{mvar|w{{prime}}}} from that column yields: {{math|(a)(aaab)(aabb)(ab)(abbb)(b)}}.

These are all of the Lyndon words whose length divides 4, in lexicographic order, so dropping the parentheses gives {{math|''B''(2,4) {{=}} aaaabaabbababbbb}}.

===Algorithm===
The following [[Python (programming language)|Python]] code calculates a de Bruijn sequence, given ''k'' and ''n'', based on an algorithm from [[Biography:Frank Ruskey|Frank Ruskey]]'s ''Combinatorial Generation''.<ref>{{cite web |title=De Bruijn sequences |url=https://github.com/sagemath/sage/blob/28da5476f102272f0b0f149ecc6bb2c2f9ece54b/src/sage/combinat/debruijn_sequence.pyx |access-date=2023-03-07 |work=Sage}}</ref>

<source lang="python">
from typing import Iterable, Union, Any
def de_bruijn(k: Union[Iterable[Any], int], n: int) -> 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(k, int):
        alphabet = list(map(str, range(k)))
    else:
        # While any sort of list becomes used as it is
        alphabet = k
        k = len(k)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1 : p + 1])
        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 "".join(alphabet[i] for i in sequence)


print(de_bruijn(2, 3))
print(de_bruijn("abcd", 2))
</source>
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,{{sfnp|Aguirre|Mattar|Magis-Weinberg|2011}} and can be specially crafted for use with [[Physics:Functional magnetic resonance imaging|functional magnetic resonance imaging]].<ref>{{cite web |url=https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software |title=de Bruijn cycle generator |access-date=2015-09-15 |archive-date=2016-01-26 |archive-url=https://web.archive.org/web/20160126133108/https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software |url-status=dead }}</ref>

===Angle detection===
The symbols of a de Bruijn sequence written around a circular object (such as a wheel of a [[Engineering:Robot|robot]]) can be used to identify its [[Angle|angle]] by examining the ''n'' consecutive symbols facing a fixed point. This angle-encoding problem is known as the "rotating drum problem".{{sfnp|van Lint|Wilson|2001}} [[Gray code]]s can be used as similar rotary positional encoding mechanisms, a method commonly found in [[Engineering:Rotary encoder|rotary encoder]]s.

===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 ("right-most 1") or the most significant set bit ("left-most 1") in a word using [[Bitwise operation|bitwise operation]]s and multiplication.<ref>{{harvtxt|Anderson|1997–2009}}; {{harvtxt|Busch|2009}}</ref> The following example uses a de Bruijn sequence to determine the index of the least significant set bit (equivalent to counting the number of trailing '0' bits) in a 32 bit unsigned integer:

<source lang="cpp">
uint8_t lowestBitIndex(uint32_t v)
{       
  static const uint8_t BitPositionLookup[32] = // hash table
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return BitPositionLookup[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
}
</source>

The <code>lowestBitIndex()</code> 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''&thinsp;(2,&nbsp;5) sequence 0000&thinsp;0111&thinsp;0111&thinsp;1100&thinsp;1011&thinsp;0101&thinsp;0011&thinsp;0001 (spaces added for clarity). The operation <code>(v & -v)</code> 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 (arithmetic modulo 2<sup>32</sup>) 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 [0, 31], which is then used as an index into [[Hash table|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:

<source lang="cpp">
uint32_t keepHighestBit(uint32_t n)
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

uint8_t highestBitIndex(uint32_t v)
{
    static const uint8_t BitPositionLookup[32] = { // hash table
         0,  1, 16,  2, 29, 17,  3, 22, 30, 20, 18, 11, 13,  4,  7, 23,
        31, 15, 28, 21, 19, 10, 12,  6, 14, 27,  9,  5, 26,  8, 25, 24,
    };
    return BitPositionLookup[(keepHighestBit(v) * 0x06EB14F9U) >> 27];
}
</source>

In the above example an alternative de Bruijn sequence (0x06EB14F9U) 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 <code>keepHighestBit()</code> 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.

===Brute-force attacks on locks===

[[File:De_Bruijn_sequence_10_4.svg|thumb|One possible ''B''&thinsp;(10,&nbsp;4) sequence. The 2530 substrings are read from top to bottom then left to right, and their digits are concatenated. To get the string to brute-force a combination lock, the last three digits in brackets (000) are appended. The 10003-digit string is hence "0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011 ... 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000" (spaces added for readability).]]
{| class="infobox wikitable collapsible collapsed" style="text-align:center;font-size:80%;line-height:0.5;"
|- style="text-align:left;font-size:125%;line-height:1;"
|colspan="10"|B{10,3} with digits read from top to bottom<br />then left to right;<ref>{{Cite web|url=http://hakank.org/comb/debruijn.cgi?k=10&n=3|title = de Bruijn (DeBruijn) sequence (K=10, n=3)}}</ref> appending "00" yields<br />a string to brute-force a 3-digit combination lock
|- style="vertical-align:top;"
|0
|rowspan="12"|1
|rowspan="23"|2
|rowspan="34"|3
|rowspan="45"|4
|rowspan="56"|5
|rowspan="67"|6
|rowspan="78"|7
|rowspan="89"|8
|rowspan="99"|9
|-
|001
|-
|002
|-
|003
|-
|004
|-
|005
|-
|006
|-
|007
|-
|008
|-
|009
|-
| 
|-
|011
|-
|012||112
|-
|013||113
|-
|014||114
|-
|015||115
|-
|016||116
|-
|017||117
|-
|018||118
|-
|019||119
|-
| 
|-
|021
|-
|022||122
|-
|023||123||223
|-
|024||124||224
|-
|025||125||225
|-
|026||126||226
|-
|027||127||227
|-
|028||128||228
|-
|029||129||229
|-
| ||rowspan="2"|
|-
|031
|-
|032||132
|-
|033||133||233
|-
|034||134||234||334
|-
|035||135||235||335
|-
|036||136||236||336
|-
|037||137||237||337
|-
|038||138||238||338
|-
|039||139||239||339
|-
| ||rowspan="2"| ||rowspan="3"|
|-
|041
|-
|042||142
|-
|043||143||243
|-
|044||144||244||344
|-
|045||145||245||345||445
|-
|046||146||246||346||446
|-
|047||147||247||347||447
|-
|048||148||248||348||448
|-
|049||149||249||349||449
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"|
|-
|051
|-
|052||152
|-
|053||153||253
|-
|054||154||254||354
|-
|055||155||255||355||455
|-
|056||156||256||356||456||556
|-
|057||157||257||357||457||557
|-
|058||158||258||358||458||558
|-
|059||159||259||359||459||559
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"|
|-
|061
|-
|062||162
|-
|063||163||263
|-
|064||164||264||364
|-
|065||165||265||365||465
|-
|066||166||266||366||466||566
|-
|067||167||267||367||467||567||667
|-
|068||168||268||368||468||568||668
|-
|069||169||269||369||469||569||669
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"|
|-
|071
|-
|072||172
|-
|073||173||273
|-
|074||174||274||374
|-
|075||175||275||375||475
|-
|076||176||276||376||476||576
|-
|077||177||277||377||477||577||677
|-
|078||178||278||378||478||578||678||778
|-
|079||179||279||379||479||579||679||779
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"| ||rowspan="7"|
|-
|081
|-
|082||182
|-
|083||183||283
|-
|084||184||284||384
|-
|085||185||285||385||485
|-
|086||186||286||386||486||586
|-
|087||187||287||387||487||587||687
|-
|088||188||288||388||488||588||688||788
|-
|089||189||289||389||489||589||689||789||889
|-
| ||rowspan="2"| ||rowspan="3"| ||rowspan="4"| ||rowspan="5"| ||rowspan="6"| ||rowspan="7"| ||rowspan="8"|
|-
|091
|-
|092||192
|-
|093||193||293
|-
|094||194||294||394
|-
|095||195||295||395||495
|-
|096||196||296||396||496||596
|-
|097||197||297||397||497||597||697
|-
|098||198||298||398||498||598||698||798
|-
|099||199||299||399||499||599||699||799||899||(00)
|}
A de Bruijn sequence can be used to shorten a brute-force attack on a PIN-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 (each digit having 10 possibilities, from 0 to 9) would have ''B''&thinsp;(10,&nbsp;4) solutions, with length {{val|10000}}. Therefore, only at most {{nowrap|{{val|10000}} + 3 {{=}} {{val|10003}}}} (as the solutions are cyclic) presses are needed to open the lock, whereas trying all codes separately would require {{nowrap|4 × {{val|10000}} {{=}} {{val|40000}}}} presses.


==f-fold de Bruijn sequences==
An '''f-fold n-ary de Bruijn sequence''' is an extension of the notion ''n''-ary de Bruijn sequence, such that the sequence of the length <math>fk^n</math> contains every possible [[Subsequence|subsequence]] of the length ''n'' exactly ''f'' times. For example, for <math>n=2</math> the cyclic sequences 11100010 and 11101000  are two-fold binary de Bruijn sequences. The number of two-fold de Bruijn sequences, <math>N_n</math> for <math>n=1</math> is <math>N_1=2</math>, the other known numbers{{sfnp|Osipov|2016}} are <math>N_2=5</math>, <math>N_3=72</math>, and <math>N_4=43768</math>.

==de Bruijn torus==
[[File:de_bruijn_torus_3x3.stl|thumb|250px|link=http://viewstl.com/classic/?embedded&url=http://upload.wikimedia.org/wikipedia/commons/1/1e/De_bruijn_torus_3x3.stl&bgcolor=black|[[STL (file format)|STL]] model of de Bruijn torus (16,32;3,3)<sub>2</sub> with 1s as panels and 0s as holes in the mesh &ndash; with consistent orientation, every 3&times;3 matrix appears exactly once]]
{{main article|De Bruijn torus}}
A [[De Bruijn torus|de Bruijn torus]] is a toroidal array with the property that every ''k''-ary ''m''-by-''n'' matrix occurs exactly once.

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 [[Analysis of algorithms|{{tmath|\color{Blue} O(n \log n)}}]] decoding algorithms exist for special, recursively constructed sequences{{sfnp|Tuliani|2001}} and extend to the two-dimensional case.{{sfnp|Hurlbert|Isaak|1993}} de Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.

==See also==
* [[Normal number]]
* [[Linear-feedback shift register]]
* ''n''-sequence
* [[BEST theorem]]
* [[Superpermutation]]

==Notes==
{{Reflist}}

==References==
* {{cite journal |last1=van Aardenne-Ehrenfest |first1=Tanja |last2=de Bruijn |first2=Nicolaas Govert |author-link2=Nicolaas Govert de Bruijn |journal=Simon Stevin |mr=0047311 |pages=203–217 |title=Circuits and trees in oriented linear graphs |url=http://alexandria.tue.nl/repository/freearticles/597493.pdf |volume=28 |date=1951}}
*{{cite journal|first1=G. K.|last1=Aguirre|first2=M. G.|last2=Mattar|first3=L.|last3=Magis-Weinberg|year=2011|url=https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn|title=de Bruijn cycles for neural decoding|journal=NeuroImage|volume=56|issue=3|pages=1293–1300|doi=10.1016/j.neuroimage.2011.02.005|pmid=21315160|pmc=3104402|access-date=2015-06-04|archive-date=2016-01-26|archive-url=https://web.archive.org/web/20160126134333/https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn|url-status=dead}}
*{{cite web |url=http://graphics.stanford.edu/~seander/bithacks.html |title=Bit Twiddling Hacks |last=Anderson |first=Sean Eron |date=1997–2009 |publisher=[[Organization:Stanford University|Stanford University]] |access-date=2009-02-12}}
* {{cite journal |last1=Berstel |first1=Jean |last2=Perrin |first2=Dominique |doi=10.1016/j.ejc.2005.07.019 |mr=2300777 |issue=3 |journal=European Journal of Combinatorics |pages=996–1022 |title=The origins of combinatorics on words |url=http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf |volume=28 |date=2007}}
*{{cite book |first=C. P. |last=Brown |date=1869 |title=Sanskrit Prosody and Numerical Symbols Explained |url=https://archive.org/stream/sanskritprosody00browgoog#page/n44/mode/2up |page=28}}
* {{cite journal |last=de Bruijn |first=Nicolaas Govert |journal=Proc. Koninklijke Nederlandse Akademie V. Wetenschappen |mr=0018142 |pages=758–764 |title=A combinatorial problem |url=http://www.dwc.knaw.nl/DL/publications/PU00018235.pdf |volume=49 |date=1946 |postscript=, ''[[Indagationes Mathematicae]]'' '''8''': 461–467}}
* {{cite book |last=de Bruijn |first=Nicolaas Govert |publisher=Technological University Eindhoven |series=T.H.-Report 75-WSK-06 |title=Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2<sup>n</sup> zeros and ones that show each n-letter word exactly once |url=http://alexandria.tue.nl/repository/books/252901.pdf |date=1975}}
*{{cite web |url=http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.html |title=Computing Trailing Zeros HOWTO |last=Busch |first=Philip |date=2009 |access-date=2015-01-29 |archive-date=2015-01-29 |archive-url=https://web.archive.org/web/20150129233016/http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.html |url-status=dead }}
*{{cite journal |last=Flye Sainte-Marie |first=Camille |journal=L'Intermédiaire des Mathématiciens |pages=107–110 |title=Solution to question nr. 48 |volume=1 |date=1894 }}
*{{cite book |title=Algebraic Shift Register Sequences |first1=Mark |last1=Goresky|first2=Andrew |last2=Klapper |publisher={{wipe|Cambridge University Press}} |date=2012 |isbn=978-1-10701499-2 |pages=174–175 |url=https://books.google.com/books?id=sd9AqHeeHh4C&pg=PA174 |contribution=8.2.5 Shift register generation of de Bruijn sequences}}
*{{cite journal |first=Rachel W. |last=Hall |url=http://www.sju.edu/~rhall/mathforpoets.pdf |title=Math for poets and drummers |journal=Math Horizons |volume=15 |issue=3 |date=2008 |pages=10–11 |doi=10.1080/10724117.2008.11974752 |s2cid=3637061 |access-date=2008-10-22 |archive-url=https://web.archive.org/web/20120212145748/http://www.sju.edu/~rhall/mathforpoets.pdf |archive-date=2012-02-12 |url-status=dead }}
*{{cite web |url=http://www.macs.hw.ac.uk/~markl/Higgins.pdf |title=Burrows-Wheeler transforms and de Bruijn words |last=Higgins |first=Peter |date=November 2012 |access-date=2017-02-11}}
* {{cite journal |last1=Hurlbert |first1=Glenn |last2=Isaak |first2=Garth |doi=10.1016/0097-3165(93)90087-O |issue=1 |journal=Journal of Combinatorial Theory |series=Series A |mr=1239511 |pages=50–62 |title=On the de Bruijn torus problem |volume=64 |date=1993 |doi-access=free }}
*{{cite journal |first=Subhash |last=Kak |date=2000 |title=Yamātārājabhānasalagāṃ an interesting combinatoric sūtra |url=http://202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf |url-status=dead |archive-url=https://web.archive.org/web/20141029120230/http://202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf |archive-date=2014-10-29 |journal=Indian Journal of History of Science |volume=35 |issue=2 |pages=123–127}}
*{{cite book |title=Stream Ciphers |first=Andreas |last=Klein |publisher=Springer |date=2013 |isbn=978-1-44715079-4 |page=59 |url=https://books.google.com/books?id=GYpEAAAAQBAJ&pg=PA59}}
*{{Cite book |date=2006 |title=The Art of Computer Programming, Fascicle 4: Generating All Trees – History of Combinatorial Generation |first=Donald Ervin |last=Knuth |publisher=Addison–Wesley |isbn=978-0-321-33570-8 |page=50 |url=https://books.google.com/books?id=56LNfE2QGtYC&pg=PA50}}
* {{cite journal |last1=Fredricksen |first1=Harold |last2=Maiorana |first2=James |doi=10.1016/0012-365X(78)90002-X |mr=523071 |issue=3 |journal=Discrete Mathematics |pages=207–210 |title=Necklaces of beads in ''k'' colors and ''k''-ary de Bruijn sequences |volume=23 |date=1978|doi-access=free }}
*{{cite journal |last=Martin |first=Monroe H. |doi=10.1090/S0002-9904-1934-05988-3 |mr=1562989 |issue=12 |journal=[[Organization:Bulletin of the American Mathematical Society|Bulletin of the American Mathematical Society]] |pages=859–864 |title=A problem in arrangements |url=https://www.ams.org/journals/bull/1934-40-12/S0002-9904-1934-05988-3/S0002-9904-1934-05988-3.pdf |volume=40 |date=1934|doi-access=free }}
* {{cite journal |last=Osipov |first=Vladimir |doi=10.1007/s10955-016-1537-5 |journal=[[Physics:Journal of Statistical Physics|Journal of Statistical Physics]] |volume=164 |issue=1 |pages=142–165 |title=Wavelet Analysis on Symbolic Sequences and Two-Fold de Bruijn Sequences |issn=1572-9613 |date=2016|arxiv=1601.02097 |bibcode=2016JSP...164..142O |s2cid=16535836 }}
*{{cite book |date=2002 |orig-year=1934 |title=The logic of scientific discovery |first=Karl |last=Popper |publisher=Routledge |isbn=978-0-415-27843-0 |page=294 |url=https://books.google.com/books?id=0a5bLBbe_dMC&pg=PA295}}
* {{cite journal |last=Ralston |first=Anthony |doi=10.2307/2690079 |issue=3 |journal=Mathematics Magazine |mr=653429 |pages=131–143 |title=de Bruijn sequences—a model example of the interaction of discrete mathematics and computer science |volume=55 |date=1982|jstor=2690079 }}
*{{cite book |first=Sherman K. |last=Stein |contribution=Yamátárájabhánasalagám |date=1963 |title=The Man-made Universe: An Introduction to the Spirit of Mathematics |pages=110–118}} Reprinted in Wardhaugh, Benjamin, ed. (2012), ''A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing'', Princeton University Press, pp. 139–144.
* {{cite journal |last=Tuliani |first=Jonathan |doi=10.1016/S0012-365X(00)00117-5 |issue=1–3 |journal=Discrete Mathematics |mr=1802599 |pages=313–336 |title=de Bruijn sequences with efficient decoding algorithms |volume=226 |date=2001|doi-access= }}
*{{cite book |title=A Course in Combinatorics |first1=J. H. |last1=van Lint|first2=Richard Michael |last2=Wilson|publisher={{wipe|Cambridge University Press}} |date=2001 |isbn=978-0-52100601-9 |page=71 |url=https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA71}}

==External links==
* {{MathWorld|urlname=deBruijnSequence|title=de Bruijn Sequence}}
* {{OEIS el|sequencenumber=A166315|name=Lexicographically smallest binary de Bruijn sequences|formalname= 	Lexicographically earliest binary de Bruijn sequences, B(2,n)}}
* [http://chessprogramming.wikispaces.com/De+Bruijn+sequence De Bruijn sequence]
* [http://www.hakank.org/comb/debruijn.cgi CGI generator]
* [http://www.hakank.org/comb/deBruijnApplet.html Applet generator]
* [https://jgeisler0303.github.io/deBruijnDecode/ Javascript generator and decoder]. Implementation of J. Tuliani's algorithm.
* [https://web.archive.org/web/20051202021442/http://www.stefangeens.com/000435.html Door code lock]
* [https://web.archive.org/web/20140527202958/http://lcni.uoregon.edu/~dow/Geek_art/Minimal_combinatorics/Minimal_arrays_containing_all_combinations.html Minimal arrays containing all sub-array combinations of symbols: de Bruijn sequences and tori]
* http://debruijnsequence.org has many kinds of de Bruijn sequences.

{{DEFAULTSORT:Bruijn sequence, de}}
[[Category:Binary sequences]]
[[Category:Enumerative combinatorics]]

{{Sourceattribution|De Bruijn sequence}}