Necklaces

The algorithm used in this file comes from

  • Sawada, Joe. “A fast algorithm to generate necklaces with fixed content”, Source Theoretical Computer Science archive Volume 301 , Issue 1-3 (May 2003)
sage.combinat.necklace.Necklaces(e)

Returns the combinatorial class of necklaces with evaluation e.

EXAMPLES:

sage: Necklaces([2,1,1])
Necklaces with evaluation [2, 1, 1]
sage: Necklaces([2,1,1]).cardinality()
3
sage: Necklaces([2,1,1]).first()
[1, 1, 2, 3]
sage: Necklaces([2,1,1]).last()
[1, 2, 1, 3]
sage: Necklaces([2,1,1]).list()
[[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3]]
class sage.combinat.necklace.Necklaces_evaluation(e)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: N = Necklaces([2,2,2])
sage: N == loads(dumps(N))
True
cardinality()

Returns the number of integer necklaces with the evaluation e.

EXAMPLES:

sage: Necklaces([]).cardinality()
0
sage: Necklaces([2,2]).cardinality()
2
sage: Necklaces([2,3,2]).cardinality()
30

Check to make sure that the count matches up with the number of Lyndon words generated.

sage: comps = [[],[2,2],[3,2,7],[4,2]]+Compositions(4).list()
sage: ns = [ Necklaces(comp) for comp in comps]
sage: all( [ n.cardinality() == len(n.list()) for n in ns] )
True

Previous topic

Lyndon words

Next topic

Non-Decreasing Parking Functions

This Page