18.17 Necklaces

Module: sage.combinat.necklace

Necklaces

Algorithm from

A fast algorithm to generate necklaces with fixed content Source Theoretical Computer Science archive Volume 301 , Issue 1-3 (May 2003) table of contents Pages: 477 - 489 Year of Publication: 2003 ISSN:0304-3975 Author Joe Sawada Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, Ont. Canada M5S 1A4 Publisher Elsevier Science Publishers Ltd. Essex, UK

Module-level Functions

Necklaces( e)

Returns the combinatorial class of necklaces with evaluation e.

sage: Necklaces([2,1,1])
Necklaces with evaluation [2, 1, 1]
sage: Necklaces([2,1,1]).count()
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: Necklaces_evaluation

class Necklaces_evaluation
Necklaces_evaluation( self, e)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

Returns the number of integer necklaces with the evaluation e.

sage: Necklaces([]).count()
0
sage: Necklaces([2,2]).count()
2
sage: Necklaces([2,3,2]).count()
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.count() == len(n.list()) for n in ns] )
True

iterator( self)

An iterator for the integer necklaces iwth evaluation e.

sage: Necklaces([]).list()    #indirect test
[]
sage: Necklaces([1]).list()   #indirect test
[[1]]
sage: Necklaces([2]).list()   #indirect test
[[1, 1]]
sage: Necklaces([3]).list()   #indirect test
[[1, 1, 1]]
sage: Necklaces([3,3]).list() #indirect test
[[1, 1, 1, 2, 2, 2],
 [1, 1, 2, 1, 2, 2],
 [1, 1, 2, 2, 1, 2],
 [1, 2, 1, 2, 1, 2]]
sage: Necklaces([2,1,3]).list() #indirect test
[[1, 1, 2, 3, 3, 3],
 [1, 1, 3, 2, 3, 3],
 [1, 1, 3, 3, 2, 3],
 [1, 1, 3, 3, 3, 2],
 [1, 2, 1, 3, 3, 3],
 [1, 2, 3, 1, 3, 3],
 [1, 2, 3, 3, 1, 3],
 [1, 3, 1, 3, 2, 3],
 [1, 3, 1, 3, 3, 2],
 [1, 3, 2, 1, 3, 3]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: [2,1,2,1] in Necklaces([2,2])
False
sage: [1,2,1,2] in Necklaces([2,2])
True
sage: [1,1,2,2] in Necklaces([2,2])
True
sage: all([ n in Necklaces([2,1,3,1]) for n in Necklaces([2,1,3,1])])
True

__repr__( self)

TESTS:

sage: repr(Necklaces([2,1,1]))
'Necklaces with evaluation [2, 1, 1]'

See About this document... for information on suggesting changes.