Editing De Bruijn sequence (section)

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