Necklaces (version 1.0)

sBruijn: The de Bruijn sequence

Description

The function generates the (minimum) de Bruijn sequence of length n over an alphabet of m consecutive non-negative integers.

Usage

sBruijn(n=1,m=2, fn=0, bSep=FALSE)

Value

string

the de Bruijn sequence

Arguments

n

positive integer: the length of the representatives

m

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

fn

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

bSep

boolean: if TRUE, a separator is inserted between the output blocks

Author

Elvira Di Nardo ,
Giuseppe Guarino

Details

The function generates the (minimum) de Bruijn sequence of order n over an alphabet of m consecutive non-negative integers. The parameter (fn) assigns the first value of the alphabet, which by default is equal to 0. If (bSep) is set equal to TRUE, a separator is inserted between the output blocks.

References

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

Necklaces, cNecklaces, LyndonW, sBruijn

Examples

# Generate the de Bruijn sequence of length 4 on the binary alphabet
# {0,1}
sBruijn(4) 
# or equivalently 
sBruijn(4,2) 

# Generate the de Bruijn sequence of length 2 over the alphabet {0,1,2} 
sBruijn(2,3)

# Generate the de Bruijn sequence of length 2 over the alphabet {1,2,3}
sBruijn(2,3,1)

# Generate the de Bruijn sequence of length 2 over the alphabet {1,2,3} 
# with a block separator. 
sBruijn(2,3,1,TRUE)