 Iterator - Maple Programming Help

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

Iterator

 Prenecklace
 generate prenecklaces

 Calling Sequence Prenecklace(n, m, opts)

Parameters

 n - posint; length of prenecklace m - posint; size of alphabet opts - (optional) equation(s) of the form option = value; specify options for the Prenecklace command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The Prenecklace 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$.
 • A prenecklace 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.

Examples

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

Create an iterator that generates all prenecklaces of length 4 in an alphabet with 2 characters.

 > $P≔\mathrm{Prenecklace}\left(4,2\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}P\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}d\n",p\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1

Compute the number of iterations.

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

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[Prenecklace] command was introduced in Maple 2020.