DeBruijn - Maple Help

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.
 • This iterator object has the common iterator methods.

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

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.