Necklace - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

# Online Help

###### All Products    Maple    MapleSim

Iterator

 Necklace
 generate necklaces

 Calling Sequence Necklace(n, m, opts)

Parameters

 n - nonnegint; length of necklace m - nonnegint; size of alphabet opts - (optional) equation(s) of the form option = value; specify options for the Necklace 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. Passing a value greater than one causes the iterator to skip the lower ranks; this can be useful when parallelizing iterators. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The Necklace command returns an iterator that generates all m-ary necklaces of length n, in lexicographic order. The alphabet consists of the integers from 0 to $m-1$; if $m=0$ the alphabet is empty.
 • The n parameter is the length of the 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

In addition to the common iterator methods, this 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

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Create an iterator that generates all necklaces of length 4 in a 2-character alphabet.

 > $P≔\mathrm{Necklace}\left(4,2\right):$
 > $\mathrm{Print}\left(P,'\mathrm{showrank}'\right):$
 1: 0 0 0 0 2: 0 0 0 1 3: 0 0 1 1 4: 0 1 0 1 5: 0 1 1 1 6: 1 1 1 1

Compute the number of iterations.

 > $\mathrm{Number}\left(P\right)$
 ${6}$ (1)

Compute the rank of an element in the sequence.

 > $\mathrm{Rank}\left(P,\left[0,1,0,1\right]\right)$
 ${4}$ (2)

Compute the necklace corresponding to a given rank.

 > $\mathrm{Unrank}\left(P,3\right)$
 $\left[\begin{array}{cccc}{0}& {0}& {1}& {1}\end{array}\right]$ (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[Necklace] command was introduced in Maple 2020.
 • For more information on Maple 2020 changes, see Updates in Maple 2020.
 • The Iterator[Necklace] command was updated in Maple 2022.
 • The n and m parameters were updated in Maple 2022.

 See Also