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 , yielding a new string Position the string above the string , and map each letter's position in to its position in while preserving order. This process defines the Standard Permutation. Write this permutation in 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 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 24 = 16, repeat the alphabet (ab) 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: . (Standard Permutation) 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, 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)