Iterator - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/DeBruijn

Iterator

 DeBruijn
 generate Lyndon words that form a de Bruijn sequence

 Calling Sequence DeBruijn(n, m, opts)

Parameters

 n - posint; maximum length of string m - posint; size of alphabet opts - (optional) equation(s) of the form option = value; specify options for the DeBruijn command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The DeBruijn command returns an iterator that generates m-ary Lyndon words, each with length less than or equal to n, that together form a de Bruijn sequence.
 • A de Bruijn sequence is a sequence of the characters 0 to $m-1$, of length ${m}^{n}$, that, when considered as a cycle, contains each string of length $n$ exactly once.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Create an iterator that generates Lyndon words with maximum length 4 in an alphabet of 3 characters.

 > $P≔\mathrm{DeBruijn}\left(4,3\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}P\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}d\n",p\left[1..\mathrm{length}\left(P\right)\right]\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 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

Combine the Lyndon words to form the de Bruijn sequence.

 > $\left[\mathrm{seq}\left(\mathrm{seq}\left(p\left[k\right],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]$ (1)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.1, generating all n-tuples, pp. 26-27.
 ibid, Algorithm F, prime and preprime string generation, p. 27.

Compatibility

 • The Iterator[DeBruijn] command was introduced in Maple 2020.
 • For more information on Maple 2020 changes, see Updates in Maple 2020.