The algorithm used in this file comes from
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]]
EXAMPLES:
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
TESTS:
sage: N = Necklaces([2,2,2])
sage: N == loads(dumps(N))
True
An iterator for the integer necklaces with evaluation e.
EXAMPLES:
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]]
TESTS:
sage: repr(Necklaces([2,1,1]))
'Necklaces with evaluation [2, 1, 1]'
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
EXAMPLES:
sage: from sage.combinat.necklace import _fast_fixed_content
sage: from sage.combinat.misc import DoublyLinkedList
sage: e = [3,3]
sage: a = [len(e)-1]*sum(e)
sage: r = [0]*sum(e)
sage: a[0] = 0
sage: e[0] -= 1
sage: k = len(e)
sage: dll = DoublyLinkedList(list(reversed(range(k))))
sage: if e[0] == 0: dll.hide(0)
sage: list(_fast_fixed_content(a,e,2,1,k,r,2,dll))
[[0, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 1, 1]]
sage: list(_fast_fixed_content(a,e,2,1,k,r,2,dll,True))
[[0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1], [0, 0, 0, 1, 1, 1]]
EXAMPLES:
sage: from sage.combinat.necklace import _ffc
sage: list(_ffc([3,3])) #necklaces
[[0, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 1, 1]]
sage: list(_ffc([3,3], equality=True)) #Lyndon words
[[0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1], [0, 0, 0, 1, 1, 1]]
EXAMPLES:
sage: from sage.combinat.necklace import _lfc
sage: list(_lfc([3,3])) #necklaces
[[0, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 1, 1]]
sage: list(_lfc([3,3], equality=True)) #Lyndon words
[[0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1], [0, 0, 0, 1, 1, 1]]
EXAMPLES:
sage: from sage.combinat.necklace import _list_fixed_content
sage: from sage.combinat.misc import DoublyLinkedList
sage: e = [3,3]
sage: a = [0]*sum(e)
sage: e[0] -= 1
sage: k = len(e)
sage: dll = DoublyLinkedList(list(reversed(range(k))))
sage: if e[0] == 0: dll.hide(0)
sage: list(_list_fixed_content(a,e,2,1,k,dll))
[[0, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 1, 1]]
sage: list(_list_fixed_content(a,e,2,1,k,dll,True))
[[0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1], [0, 0, 0, 1, 1, 1]]
Returns the length of the longest prefix of w that is a Lyndon word.
EXAMPLES:
sage: import sage.combinat.necklace as necklace
sage: necklace._lyn([0,1,1,0,0,1,2])
3
sage: necklace._lyn([0,0,0,1])
4
sage: necklace._lyn([2,1,0,0,2,2,1])
1
This function sets things up and calls _simple_fixed_content.
EXAMPLES:
sage: from sage.combinat.necklace import _sfc
sage: list(_sfc([3,3])) #necklaces
[[0, 0, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 1, 0, 1, 0, 1]]
sage: list(_sfc([3,3], equality=True)) #Lyndon words
[[0, 0, 0, 1, 1, 1], [0, 0, 1, 0, 1, 1], [0, 0, 1, 1, 0, 1]]
EXAMPLES:
sage: from sage.combinat.necklace import _simple_fixed_content
sage: content = [3,3]
sage: a = [0]*sum(content)
sage: content[0] -= 1
sage: k = len(content); k
2
sage: list(_simple_fixed_content(a, content, 2, 1, k))
[[0, 0, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 1, 0, 1, 0, 1]]
sage: list(_simple_fixed_content(a, content, 2, 1, k, True))
[[0, 0, 0, 1, 1, 1], [0, 0, 1, 0, 1, 1], [0, 0, 1, 1, 0, 1]]