combinat::necklaces::fromEvaluation – necklaces with prescribed evaluation

The combinatorial class of integral necklaces with prescribed evaluation

→ Examples

Superdomain

Dom::BaseDomain

Axioms

Ax::systemRep

Details:

• An integer necklace is a necklace whose operands are positive integers.

• The evaluation of a necklace w is a list c such that c[i] is the number of occurrences of the letter i in w. For example, the evaluation of [1,1,1,2,1,3,3] is [4,1,2]. See combinat::words::evaluation for details.

• Some functions here only deal with evaluations that are compositions. In other words the corresponding Lyndon words should contain all the integers in a range 1..k (counter examples: [2,2,3] or [1,4,3,3]).

isA – test if an object is a necklace

combinat::necklaces::fromEvaluation::isA(any type object, <composition evaluation>)

Returns whether object is a necklace.

If the optional argument is present, returns whether object is a necklace with evaluation evaluation.

count – number of integer necklaces with prescribed evaluation

combinat::necklaces::fromEvaluation::count(integer list evaluation)

Returns the number of integer necklaces with evaluation evaluation.

list – list of the integer necklaces with prescribed evaluation

combinat::necklaces::fromEvaluation::list(composition evaluation)

Returns the list of the integer necklaces with evaluation evaluation.

generator – generator for the integer necklaces with prescribed evaluation

combinat::necklaces::fromEvaluation::generator(composition evaluation)

Returns a generator for the integer necklaces with evaluation evaluation.

Example 1:

Background:

• The generation algorithm for necklaces with prescribed evaluation is guaranteed to be constant time amortized for each necklace generated if the last entry of the evaluation is the largest one. As a consequence, to generate all the necklaces with letters [2,2,2,1,1], it is more efficient to generate the necklaces with letters [1,1,2,2,2], and to relabel them accordingly afterward. Of course, the downside is that the resulting necklaces are not in canonical form.

• Reference: Joe Sawada, A fast algorithm to generate necklaces with fixed content, Theoretical Computer Science, 2003, 301, pp. 477-489.

• As far as we can tell, there is no known good algorithm for unranking necklaces and Lyndon words with prescribed evaluation.

Changes in MuPAD 3.1

New Function.