LyndonW {Necklaces}

Lyndon words

Description

The function generates Lyndon words from necklaces of length n over an alphabet of m consecutive non-negative integers.

Usage

LyndonW(n=1, m=2, bOut=FALSE, fn=1)

Arguments

n

positive integer: the length of the representatives

m

positive integer: the number of consecutive non-negative integers in the alphabet

bOut

boolean: if TRUE, the function produces a compact result

fn

integer: the first value of the alphabet, the default is 1

Details

The function generates Lyndon words from necklaces of length n over an alphabet of m consecutive non-negative integers. The last parameter (fn) initializes the first value of the alphabet, which by default is equal to 1. If the parameter (bOut) is set equal to TRUE, the function produces a compact result. As example, running LyndonW(5,2, TRUE,0), the function generates Lyndon words in compact form, from the binary necklaces of length 5, that are [0 0 0 0 1], [0 0 0 1 1], [0 0 1 0 1], [0 0 1 1 1], [0 1 0 1 1], [0 1 1 1 1].

Value

list

the list containing all the Lyndon words of length n over an alphabet of m consecutive non-negative integers.

Note

The function calls the cNecklaces and lSort functions in the Necklaces package.

Author(s)

Elvira Di Nardo [e-mail],
Giuseppe Guarino [e-mail]

References

Di Nardo, E. (2014) On a symbolic representation of non-central Wishart random matrices with applications. Jour. Mult. Anal. Vol.125, 121–135. (https://arxiv.org/abs/1312.4395)

Di Nardo, E., and Guarino., G. (2022) Necklaces and bracelets in R - (https://arxiv.org/abs/2208.06855)

Flajolet, P., and Sedgewick, R. (2009) Analytic combinatorics. Cambridge University press.

See Also

cNecklaces, sBruijn

Examples

# Generate all the Lyndon words of length 5 over the alphabet 
# {1,2} 
LyndonW(5) 
# or equivalently 
LyndonW(5,2) 

# The previous result in a compact form 
LyndonW(5,2,TRUE)

# Generate all the Lyndon words of length 5 over the alphabet 
# {0,1}
LyndonW(5,2,TRUE,0)