Finite words¶
Finite words
Methods that are not in Sage (for now!)
AUTHORS:
- Sébastien Labbé, 2015
- Sébastien Labbé, 2017, added lexicographic Lyndon stuff
EXAMPLES:
sage: from slabbe.finite_word import discrepancy
sage: w = words.ChristoffelWord(5,8)
sage: discrepancy(w)
12/13
-
slabbe.finite_word.
are_overlapping_factors
(u, v, d)¶ Returns whether there exists a word w such that u occurs in w at position 0 and v occurs in w at position d.
INPUT:
u
– wordv
– wordd
– integer (positive or negative)
EXAMPLES:
sage: from slabbe.finite_word import are_overlapping_factors sage: are_overlapping_factors('abc', 'abc', 0) True sage: are_overlapping_factors('abc', 'abc', 1) False sage: are_overlapping_factors('abcdef', 'bc', 1) True sage: are_overlapping_factors('abcdef', 'bcdefgh', 1) True sage: are_overlapping_factors('abcdef', 'bcddefgh', 1) False sage: are_overlapping_factors('abcdef', 'aabcdefgh', -1) True sage: are_overlapping_factors('abcdef', 'aabcd', -1) True sage: are_overlapping_factors('abcdef', 'aabcc', -1) False
-
slabbe.finite_word.
discrepancy
(self, freq=None)¶ Return the discrepancy of the word.
This is a distance to the euclidean line defined in [T1980].
INPUT:
freq
– frequency vector (default:None
)
EXAMPLES:
sage: from slabbe.finite_word import discrepancy sage: w = words.ChristoffelWord(5,8) sage: w word: 0010010100101 sage: discrepancy(w) 12/13
sage: for c in w.conjugates(): print (c, discrepancy(c)) 0010010100101 12/13 0100101001010 7/13 1001010010100 10/13 0010100101001 10/13 0101001010010 7/13 1010010100100 12/13 0100101001001 8/13 1001010010010 9/13 0010100100101 11/13 0101001001010 6/13 1010010010100 11/13 0100100101001 9/13 1001001010010 8/13
REFERENCES:
[T1980] R., Tijdeman. The chairman assignment problem. Discrete Mathematics 32, no 3 (1980): 323-30. doi:10.1016/0012-365X(80)90269-1.
-
slabbe.finite_word.
is_lyndon_mod_reverse
(self)¶ EXAMPLES:
sage: from slabbe.finite_word import is_lyndon_mod_reverse sage: is_lyndon_mod_reverse(Word('111222')) True sage: is_lyndon_mod_reverse(Word('1112221')) False sage: is_lyndon_mod_reverse(Word('143')) False
sage: w = words.ChristoffelWord(72452,462443) sage: is_lyndon_mod_reverse(w) True
-
slabbe.finite_word.
minimum_lexicographic_conjugate
(self)¶ Return the conjugate word which is minimal for the lexicographic order.
The output is a Lyndon word (or some power of).
EXAMPLES:
sage: from slabbe.finite_word import minimum_lexicographic_conjugate sage: minimum_lexicographic_conjugate(Word([1,3,2,2,2])) word: 13222 sage: minimum_lexicographic_conjugate(Word([1,4,3])) word: 143 sage: minimum_lexicographic_conjugate(Word([3,4,1])) word: 134
The code is fast:
sage: w = words.ChristoffelWord(72452, 462443) sage: minimum_lexicographic_conjugate(w) word: 0000000100000010000000100000010000001000...
-
slabbe.finite_word.
minimum_lexicographic_conjugate_reversal
(self)¶ TODO: Use Lyndon factorisation to improve the time/space…
EXAMPLES:
sage: from slabbe.finite_word import minimum_lexicographic_conjugate_reversal sage: minimum_lexicographic_conjugate_reversal(Word([1,3,2,2,2])) word: 12223
sage: w = words.ChristoffelWord(72452,462443) sage: minimum_lexicographic_conjugate_reversal(w) word: 0000000100000010000000100000010000001000... sage: _ == w True sage: minimum_lexicographic_conjugate_reversal(Word([1,3,2,2,1,1,2])) word: 1121322
-
slabbe.finite_word.
run_length_encoding
(self)¶ EXAMPLES:
sage: from slabbe.finite_word import run_length_encoding sage: L = [0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3] sage: run_length_encoding(L) [(0, 1), (1, 6), (2, 1), (1, 1), (2, 5), (3, 6)]
-
slabbe.finite_word.
sort_word_by_length_lex_key
(w)¶ A key function to sort word (by length, and then lexicographically).
EXAMPLES:
sage: from slabbe.finite_word import sort_word_by_length_lex_key sage: L = ['aa', 'aaa', 'bb', 'ccc'] sage: sorted(L, key=sort_word_by_length_lex_key) ['aa', 'bb', 'aaa', 'ccc']
-
slabbe.finite_word.
to_image
(self, width=1000)¶ Creates an image from a word
INPUT:
width
– integer, width of image
EXAMPLES:
sage: from slabbe.finite_word import to_image sage: t = words.ThueMorseWord() sage: img = to_image(t[:10000], width=100) sage: img <PIL.Image.Image image mode=RGB size=100x100 at 0x...> sage: img.show() # not tested
sage: W = FiniteWords(range(10)) sage: d = {a:W.random_element(7) for a in range(10)} sage: m = WordMorphism(d, codomain=W) sage: w = m.periodic_points()[0][0]
sage: s = str(pi.n(digits=40001))[2:] sage: s = [int(a) for a in s] sage: len(s) 40000 sage: img = to_image(W(s), 200) sage: img.show() # not tested
-
slabbe.finite_word.
word_to_polyomino
(self)¶ Returns the inside points of a polyomino.
INPUT:
self
– list of integers in 0,1,2,3 describing a closed path
OUTPUT:
- list of 2d vectors
EXAMPLES:
sage: from slabbe.finite_word import word_to_polyomino sage: w = [0,0,0,1,1,1,2,2,2,3,3,3] sage: sorted(word_to_polyomino(w)) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)] sage: w = [1,1,1,0,0,0,3,3,3,2,2,2] sage: sorted(word_to_polyomino(w)) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]