Iterator
DeBruijn
generate Lyndon words that form a de Bruijn sequence
Calling Sequence
Parameters
Options
Description
Examples
References
Compatibility
DeBruijn(n, m, opts)
n

nonnegint; maximum length of string
m
nonnegint; size of alphabet
opts
(optional) equation(s) of the form option = value; specify options for the DeBruijn command
compile = truefalse
True means compile the iterator. The default is true.
The DeBruijn command returns an iterator that generates mary Lyndon words, each with $0<\mathrm{length}\le n$, that together form a de Bruijn sequence.
A de Bruijn sequence is a sequence of the characters 0 to $m1$, of length ${m}^{n}$, that, when considered as a cycle, contains each string of length $n$ exactly once.
Methods
In addition to the common iterator methods, this iterator object has the following methods. The self parameter is the iterator object.
Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.
$\mathrm{with}\left(\mathrm{Iterator}\right)\:$
Create an iterator that generates Lyndon words with maximum length 4 in an alphabet of 3 characters.
$P\u2254\mathrm{DeBruijn}\left(4\,3\right)\:$
$\mathrm{Print}\left(P\,\'\mathrm{showrank}\'\right)\:$
1: 0 2: 0 0 0 1 3: 0 0 0 2 4: 0 0 1 1 5: 0 0 1 2 6: 0 0 2 1 7: 0 0 2 2 8: 0 1 9: 0 1 0 2 10: 0 1 1 1 11: 0 1 1 2 12: 0 1 2 1 13: 0 1 2 2 14: 0 2 15: 0 2 1 1 16: 0 2 1 2 17: 0 2 2 1 18: 0 2 2 2 19: 1 20: 1 1 1 2 21: 1 1 2 2 22: 1 2 23: 1 2 2 2 24: 2
Compute the number of iterations.
Combine the Lyndon words to form the de Bruijn sequence.
$\left[\mathrm{seq}\left(\mathrm{seq}\left({p}_{k}\,k\=1..\mathrm{length}\left(P\right)\right)\,p\=P\right)\right]$
$\left[{0}{\,}{0}{\,}{0}{\,}{0}{\,}{1}{\,}{0}{\,}{0}{\,}{0}{\,}{2}{\,}{0}{\,}{0}{\,}{1}{\,}{1}{\,}{0}{\,}{0}{\,}{1}{\,}{2}{\,}{0}{\,}{0}{\,}{2}{\,}{1}{\,}{0}{\,}{0}{\,}{2}{\,}{2}{\,}{0}{\,}{1}{\,}{0}{\,}{1}{\,}{0}{\,}{2}{\,}{0}{\,}{1}{\,}{1}{\,}{1}{\,}{0}{\,}{1}{\,}{1}{\,}{2}{\,}{0}{\,}{1}{\,}{2}{\,}{1}{\,}{0}{\,}{1}{\,}{2}{\,}{2}{\,}{0}{\,}{2}{\,}{0}{\,}{2}{\,}{1}{\,}{1}{\,}{0}{\,}{2}{\,}{1}{\,}{2}{\,}{0}{\,}{2}{\,}{2}{\,}{1}{\,}{0}{\,}{2}{\,}{2}{\,}{2}{\,}{1}{\,}{1}{\,}{1}{\,}{1}{\,}{2}{\,}{1}{\,}{1}{\,}{2}{\,}{2}{\,}{1}{\,}{2}{\,}{1}{\,}{2}{\,}{2}{\,}{2}{\,}{2}\right]$
Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.1, generating all ntuples, pp. 2627.
ibid, Algorithm F, prime and preprime string generation, p. 27.
The Iterator[DeBruijn] command was introduced in Maple 2020.
For more information on Maple 2020 changes, see Updates in Maple 2020.
The Iterator[DeBruijn] command was updated in Maple 2022.
The n and m parameters were updated in Maple 2022.
See Also
LyndonWord
Necklace
Prenecklace
Download Help Document