Module: sage.combinat.lyndon_word
Lyndon words
Module-level Functions
e, [k=None]) |
Returns the combinatorial class of Lyndon words.
If e is an integer, then e specifies the length of the alphabet; k must also be specified in this case.
sage: LW = LyndonWords(3,3); LW Lyndon words from an alphabet of size 3 of length 3 sage: LW.first() [1, 1, 2] sage: LW.last() [2, 3, 3] sage: LW.random_element() [1, 1, 2] sage: LW.count() 8
If e is a (weak) composition, then it returns the class of Lyndon words that have evaluation e.
sage: LyndonWords([2, 0, 1]).list() [[1, 1, 3]] sage: LyndonWords([2, 0, 1, 0, 1]).list() [[1, 1, 3, 5], [1, 1, 5, 3], [1, 3, 1, 5]] sage: LyndonWords([2, 1, 1]).list() [[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3]]
n, k) |
Returns the combinatorial class of standard bracketed Lyndon words from [1, ..., n] of length k. These are in one to one correspondence with the Lyndon words and form a basis for the subspace of degree k of the free Lie algebra of rank n.
sage: SBLW33 = StandardBracketedLyndonWords(3,3); SBLW33 Standard bracketed Lyndon words from an alphabet of size 3 of length 3 sage: SBLW33.first() [1, [1, 2]] sage: SBLW33.last() [[2, 3], 3] sage: SBLW33.count() 8 sage: SBLW33.random_element() [1, [1, 2]]
lw) |
Returns the standard bracketing of a Lyndon word lw.
sage: import sage.combinat.lyndon_word as lyndon_word sage: map( lyndon_word.standard_bracketing, LyndonWords(3,3) ) [[1, [1, 2]], [1, [1, 3]], [[1, 2], 2], [1, [2, 3]], [[1, 3], 2], [[1, 3], 3], [2, [2, 3]], [[2, 3], 3]]
Class: LyndonWords_evaluation
self, e) |
TESTS:
sage: LW21 = LyndonWords([2,1]); LW21 Lyndon words with evaluation [2, 1] sage: LW21 == loads(dumps(LW21)) True
Functions: count,
iterator
self) |
Returns the number of Lyndon words with the evaluation e.
sage: LyndonWords([]).count() 0 sage: LyndonWords([2,2]).count() 1 sage: LyndonWords([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: lws = [ LyndonWords(comp) for comp in comps] sage: all( [ lw.count() == len(lw.list()) for lw in lws] ) True
self) |
An iterator for the Lyndon words with evaluation e.
sage: LyndonWords([1]).list() #indirect doctest [[1]] sage: LyndonWords([2]).list() #indirect doctest [] sage: LyndonWords([3]).list() #indirect doctest [] sage: LyndonWords([3,1]).list() #indirect doctest [[1, 1, 1, 2]] sage: LyndonWords([2,2]).list() #indirect doctest [[1, 1, 2, 2]] sage: LyndonWords([1,3]).list() #indirect doctest [[1, 2, 2, 2]] sage: LyndonWords([3,3]).list() #indirect doctest [[1, 1, 1, 2, 2, 2], [1, 1, 2, 1, 2, 2], [1, 1, 2, 2, 1, 2]] sage: LyndonWords([4,3]).list() #indirect doctest [[1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 2, 1, 2, 2], [1, 1, 1, 2, 2, 1, 2], [1, 1, 2, 1, 1, 2, 2], [1, 1, 2, 1, 2, 1, 2]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
sage: [1,2,1,2] in LyndonWords([2,2]) False sage: [1,1,2,2] in LyndonWords([2,2]) True sage: all([ lw in LyndonWords([2,1,3,1]) for lw in LyndonWords([2,1,3,1])]) True
self) |
TESTS:
sage: repr(LyndonWords([2,1,1])) 'Lyndon words with evaluation [2, 1, 1]'
Class: LyndonWords_nk
self, n, k) |
TESTS:
sage: LW23 = LyndonWords(2,3); LW23 Lyndon words from an alphabet of size 2 of length 3 sage: LW23== loads(dumps(LW23)) True
Functions: count,
iterator
self) |
TESTS:
sage: [ LyndonWords(3,i).count() for i in range(1, 11) ] [3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880]
self) |
TESTS:
sage: LyndonWords(3,3).list() # indirect doctest [[1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 2], [1, 3, 3], [2, 2, 3], [2, 3, 3]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: LW33 = LyndonWords(3,3) sage: all([lw in LW33 for lw in LW33]) True
self) |
TESTS:
sage: repr(LyndonWords(2, 3)) 'Lyndon words from an alphabet of size 2 of length 3'
Class: StandardBracketedLyndonWords_nk
self, n, k) |
TESTS:
sage: SBLW = StandardBracketedLyndonWords(3, 2) sage: SBLW == loads(dumps(SBLW)) True
Functions: count,
iterator
self) |
sage: StandardBracketedLyndonWords(3, 3).count() 8 sage: StandardBracketedLyndonWords(3, 4).count() 18
self) |
sage: StandardBracketedLyndonWords(3, 3).list() [[1, [1, 2]], [1, [1, 3]], [[1, 2], 2], [1, [2, 3]], [[1, 3], 2], [[1, 3], 3], [2, [2, 3]], [[2, 3], 3]]
Special Functions: __init__,
__repr__
self) |
TESTS:
sage: repr(StandardBracketedLyndonWords(3, 3)) 'Standard bracketed Lyndon words from an alphabet of size 3 of length 3'