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(content)¶ 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
INPUT:
content– a list or tuple of non-negative 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]]
-
class
sage.combinat.necklace.Necklaces_evaluation(content)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation,sage.structure.parent.ParentNecklaces with a fixed evaluation (content).
INPUT:
content– a list or tuple of non-negative integers
-
cardinality()¶ 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
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) True
-
content()¶ Return the content (or evaluation) of the necklaces.