Necklaces {Necklaces}

Necklaces

Description

The function generates all the representatives of all the necklaces of length n over an alphabet of m consecutive non-negative integers.

Usage

Necklaces(n=1, m=1, fn=1)

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 1

Details

The function generates the list of all representatives of all necklaces having a fixed length n on the same alphabet, by default {1,2,...,m}. The main block function is the fNecklaces function of the Necklaces package, which is called repeatedly. The input parameters of the fNecklaces function are generated by using the mKT function of the kStatistics package. Indeed, given a multi-index v, that is a vector of non-negative integers, and a positive integer n, the mKT function returns all the lists (v1,...,vn) of non-negative integer vectors, having the same length of the multi-index v and such that v=v1+...+vn. Here, the mKT function is used with the input vector having length 1 as well as the output vectors v1,...,vn, corresponding to the partitions of an integer with a fixed number of parts. As example, the mKT function with input (3,3) generates the following result:

[( 1 )( 1 )( 1 )]

[( 0 )( 1 )( 2 )]

[( 1 )( 0 )( 2 )]

[( 1 )( 2 )( 0 )]

[( 0 )( 2 )( 1 )]

[( 2 )( 0 )( 1 )]

[( 2 )( 1 )( 0 )]

[( 0 )( 3 )( 0 )]

[( 3 )( 0 )( 0 )]

[( 0 )( 0 )( 3 )]

Each vector is a possible configuration and then passed to the fNecklaces function to recover the corresponding necklace. For example

• the configuration [( 1 )( 1 )( 1 )] denotes the vector [1,2,3]; calling fNecklaces(c(1,1,1)), the representatives [1,2,3] and [1,3,2] are generated;
  

• the configuration [( 0 )( 1 )( 2 )] denotes the vector [2,3,3]; calling fNecklaces(c(0,1,2)), the reprsentative [2,3,3] is generated
  

• the configuration [( 1 )( 0 )( 2 )] denotes the vector [1,3,3]; calling fNecklaces(c(1,0,2)), the representative [1,3,3] is generated;

and so on. As last step, the union of all the outputs gives the expected result:

[ 1 1 1 ], [ 1 1 2 ], [ 1 1 3 ], [ 1 2 2 ], [ 1 2 3 ], [ 1 3 2 ], [ 1 3 3 ], [ 2 2 2 ], [ 2 2 3 ], [ 2 3 3 ], [ 3 3 3 ]

that are all the representatives of necklaces of length 3 on the alphabet {1,2,3}.

Value

list

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

Note

The function calls the fNecklaces function in the Necklaces package and the mKT functions in the kStatistics package.

Author(s)

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

References

Di Nardo, E., and Guarino., G. (2022) kStatistics: Unbiased Estimates of Joint Cumulant Products from the Multivariate Faa Di Bruno's Formula. The R journal - In press. (https://arxiv.org/abs/2206.15348)

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

fNecklaces, LyndonW, sBruijn

Examples

# Generate the list of all the representatives of all the necklaces 
# of length 4 over the alphabet {1,2}. 
Necklaces(4,2)  


# Generate the list of  all the representatives of all the necklaces 
# of length 5 over the alphabet {1,2,3}. 
Necklaces(5,3)  


# Generate the list of  all the representatives of all the necklaces 
# of length 5 over the alphabet {0,1,2}. 
Necklaces(5,3,0)