Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Iterator

  

LyndonWord

  

generate Lyndon words

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

Calling Sequence

LyndonWord(n, m, opts)

Parameters

n

-

posint; length of string

m

-

posint; size of alphabet

opts

-

(optional) equation(s) of the form option = value; specify options for the LyndonWord command

Options

• 

compile = truefalse

  

True means compile the iterator. The default is true.

• 

rank = nonnegint

  

Specify the starting rank of the iterator. The default is one. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

• 

The LyndonWord command returns an iterator that generates all m-ary Lyndon words of length n, in lexicographic order. The alphabet consists of the integers from 0 to m1.

• 

A Lyndon word is an aperiodic necklace. A necklace is an equivalence class of strings under rotation. The representative of a class is the smallest string, lexicographically, in the class.

Methods

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

• 

Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.

• 

Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

withIterator:

Create an iterator that generates all Lyndon words of length 4 in a 3-character alphabet.

PLyndonWord4,3:

forpinPdoprintf%{}d\n,penddo

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 2
0 1 1 1
0 1 1 2
0 1 2 1
0 1 2 2
0 2 1 1
0 2 1 2
0 2 2 1
0 2 2 2
1 1 1 2
1 1 2 2
1 2 2 2

Compute the number of iterations.

NumberP

18

(1)

Compute the rank of an element in the sequence.

RankP,0,1,1,2

9

(2)

Compute the Lyndon word corresponding to a given rank.

UnrankP,5

0021

(3)

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.

  

Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences, Joe Sawada and Aaron Williams, Journal of Discrete Algorithms, vol. 43, March 2017, pp. 95-110.

Compatibility

• 

The Iterator[LyndonWord] command was introduced in Maple 2020.

• 

For more information on Maple 2020 changes, see Updates in Maple 2020.

See Also

Iterator

Necklace

Prenecklace