Editing De Bruijn sequence (section)

== 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]] 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 word]]s 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]]s{{sfnp|Goresky|Klapper|2012}} or via [[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]]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 [[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>

<syntaxhighlight lang="python">
from typing import Iterable, Any
def de_bruijn(k: Iterable[str] | 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))
</syntaxhighlight>
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.