DeBruijn - Maple Help

Iterator

 DeBruijn
 generate Lyndon words that form a de Bruijn sequence

 Calling Sequence DeBruijn(n, m, opts)

Parameters

 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

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 $0<\mathrm{length}\le 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.

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.

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):$
 > $\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\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.