Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Iterator

  

DeBruijn

  

generate Lyndon words that form a de Bruijn sequence

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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 m1, of length mn, that, when considered as a cycle, contains each string of length n exactly once.

Examples

withIterator:

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

PDeBruijn4,3:

forpinPdoprintf%{}d\n,p1..lengthPenddo:

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.

seqseqpk,k=1..lengthP,p=P

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

(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.

See Also

Iterator

LyndonWord

Necklace

Prenecklace