Necklaces

The algorithm used in this file comes from

  • Sawada, Joe. A fast algorithm to generate necklaces with fixed content, Theoretical Computer Science archive Volume 301, Issue 1-3 (May 2003) doi:10.1016/S0304-3975(03)00049-5

sage.combinat.necklace.Necklaces(content)[source]

Return the set of necklaces with evaluation content.

A necklace is a list of integers that such that the list is the smallest lexicographic representative of all the cyclic shifts of the list.

See also

LyndonWords

INPUT:

  • content – list or tuple of nonnegative integers

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]]
sage: Necklaces([0,2,1,1]).list()
[[2, 2, 3, 4], [2, 2, 4, 3], [2, 3, 2, 4]]
sage: Necklaces([2,0,1,1]).list()
[[1, 1, 3, 4], [1, 1, 4, 3], [1, 3, 1, 4]]

>>> from sage.all import *
>>> Necklaces([Integer(2),Integer(1),Integer(1)])
Necklaces with evaluation [2, 1, 1]
>>> Necklaces([Integer(2),Integer(1),Integer(1)]).cardinality()
3
>>> Necklaces([Integer(2),Integer(1),Integer(1)]).first()
[1, 1, 2, 3]
>>> Necklaces([Integer(2),Integer(1),Integer(1)]).last()
[1, 2, 1, 3]
>>> Necklaces([Integer(2),Integer(1),Integer(1)]).list()
[[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3]]
>>> Necklaces([Integer(0),Integer(2),Integer(1),Integer(1)]).list()
[[2, 2, 3, 4], [2, 2, 4, 3], [2, 3, 2, 4]]
>>> Necklaces([Integer(2),Integer(0),Integer(1),Integer(1)]).list()
[[1, 1, 3, 4], [1, 1, 4, 3], [1, 3, 1, 4]]
class sage.combinat.necklace.Necklaces_evaluation(content)[source]

Bases: UniqueRepresentation, Parent

Necklaces with a fixed evaluation (content).

INPUT:

  • content – list or tuple of nonnegative integers

cardinality()[source]

Return the number of integer necklaces with the evaluation content.

The formula for the number of necklaces of content \(\alpha\) a composition of \(n\) is:

\[\sum_{d|gcd(\alpha)} \phi(d) \binom{n/d}{\alpha_1/d, \ldots, \alpha_\ell/d},\]

where \(\phi(d)\) is the Euler \(\phi\) function.

EXAMPLES:

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

>>> from sage.all import *
>>> Necklaces([]).cardinality()
0
>>> Necklaces([Integer(2),Integer(2)]).cardinality()
2
>>> Necklaces([Integer(2),Integer(3),Integer(2)]).cardinality()
30
>>> Necklaces([Integer(0),Integer(3),Integer(2)]).cardinality()
2

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

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

>>> from sage.all import *
>>> comps = [[],[Integer(2),Integer(2)],[Integer(3),Integer(2),Integer(7)],[Integer(4),Integer(2)],[Integer(0),Integer(4),Integer(2)],[Integer(2),Integer(0),Integer(4)]] + Compositions(Integer(4)).list()
>>> ns = [Necklaces(comp) for comp in comps]
>>> all(n.cardinality() == len(n.list()) for n in ns)                     # needs sage.libs.pari
True
content()[source]

Return the content (or evaluation) of the necklaces.

EXAMPLES:

sage: N = Necklaces([2,2,2])
sage: N.content()
[2, 2, 2]

>>> from sage.all import *
>>> N = Necklaces([Integer(2),Integer(2),Integer(2)])
>>> N.content()
[2, 2, 2]