Fast word datatype using an array of unsigned char¶

class sage.combinat.words.word_char.WordDatatype_char[source]¶

Bases: WordDatatype

A Fast class for words represented by an array unsigned char *.

Currently, only handles letters in [0,255].

concatenate(other)[source]¶

Concatenation of self and other.

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: W([0,2,1]).concatenate([0,0,0])
word: 021000

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> W([Integer(0),Integer(2),Integer(1)]).concatenate([Integer(0),Integer(0),Integer(0)])
word: 021000

Sage Live

W = Words([0,1,2])
W([0,2,1]).concatenate([0,0,0])

has_prefix(other)[source]¶

Test whether other is a prefix of self.

INPUT:

other – a word or a sequence (e.g. tuple, list)

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: w = W([0,1,1,0,1,2,0])
sage: w.has_prefix([0,1,1])
True
sage: w.has_prefix([0,1,2])
False
sage: w.has_prefix(w)
True
sage: w.has_prefix(w[:-1])
True
sage: w.has_prefix(w[1:])
False

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> w = W([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(2),Integer(0)])
>>> w.has_prefix([Integer(0),Integer(1),Integer(1)])
True
>>> w.has_prefix([Integer(0),Integer(1),Integer(2)])
False
>>> w.has_prefix(w)
True
>>> w.has_prefix(w[:-Integer(1)])
True
>>> w.has_prefix(w[Integer(1):])
False

Sage Live

W = Words([0,1,2])
w = W([0,1,1,0,1,2,0])
w.has_prefix([0,1,1])
w.has_prefix([0,1,2])
w.has_prefix(w)
w.has_prefix(w[:-1])
w.has_prefix(w[1:])

is_empty()[source]¶

Return whether the word is empty.

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: W([0,1,2,2]).is_empty()
False
sage: W([]).is_empty()
True

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> W([Integer(0),Integer(1),Integer(2),Integer(2)]).is_empty()
False
>>> W([]).is_empty()
True

Sage Live

W = Words([0,1,2])
W([0,1,2,2]).is_empty()
W([]).is_empty()

is_square()[source]¶

Return True if self is a square, and False otherwise.

EXAMPLES:

Sage

sage: w = Word([n % 4 for n in range(48)], alphabet=[0,1,2,3])
sage: w.is_square()
True

Python

>>> from sage.all import *
>>> w = Word([n % Integer(4) for n in range(Integer(48))], alphabet=[Integer(0),Integer(1),Integer(2),Integer(3)])
>>> w.is_square()
True

Sage Live

w = Word([n % 4 for n in range(48)], alphabet=[0,1,2,3])
w.is_square()

Sage

sage: w = Word([n % 4 for n in range(49)], alphabet=[0,1,2,3])
sage: w.is_square()
False
sage: (w*w).is_square()
True

Python

>>> from sage.all import *
>>> w = Word([n % Integer(4) for n in range(Integer(49))], alphabet=[Integer(0),Integer(1),Integer(2),Integer(3)])
>>> w.is_square()
False
>>> (w*w).is_square()
True

Sage Live

w = Word([n % 4 for n in range(49)], alphabet=[0,1,2,3])
w.is_square()
(w*w).is_square()

Python

>>> from sage.all import *
>>> w = Word([n % Integer(4) for n in range(Integer(49))], alphabet=[Integer(0),Integer(1),Integer(2),Integer(3)])
>>> w.is_square()
False
>>> (w*w).is_square()
True

Sage Live

w = Word([n % 4 for n in range(49)], alphabet=[0,1,2,3])
w.is_square()
(w*w).is_square()

length()[source]¶

Return the length of the word as a Sage integer.

EXAMPLES:

Sage

sage: W = Words([0,1,2,3,4])
sage: w = W([0,1,2,0,3,2,1])
sage: w.length()
7
sage: type(w.length())
<class 'sage.rings.integer.Integer'>
sage: type(len(w))
<class 'int'>

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2),Integer(3),Integer(4)])
>>> w = W([Integer(0),Integer(1),Integer(2),Integer(0),Integer(3),Integer(2),Integer(1)])
>>> w.length()
7
>>> type(w.length())
<class 'sage.rings.integer.Integer'>
>>> type(len(w))
<class 'int'>

Sage Live

W = Words([0,1,2,3,4])
w = W([0,1,2,0,3,2,1])
w.length()
type(w.length())
type(len(w))

letters()[source]¶

Return the list of letters that appear in this word, listed in the order of first appearance.

EXAMPLES:

Sage

sage: W = Words(5)
sage: W([1,3,1,2,2,3,1]).letters()
[1, 3, 2]

Python

>>> from sage.all import *
>>> W = Words(Integer(5))
>>> W([Integer(1),Integer(3),Integer(1),Integer(2),Integer(2),Integer(3),Integer(1)]).letters()
[1, 3, 2]

Sage Live

W = Words(5)
W([1,3,1,2,2,3,1]).letters()

longest_common_prefix(other)[source]¶

Return the longest common prefix of this word and other.

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: W([0,1,0,2]).longest_common_prefix([0,1])
word: 01
sage: u = W([0,1,0,0,1])
sage: v = W([0,1,0,2])
sage: u.longest_common_prefix(v)
word: 010
sage: v.longest_common_prefix(u)
word: 010

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> W([Integer(0),Integer(1),Integer(0),Integer(2)]).longest_common_prefix([Integer(0),Integer(1)])
word: 01
>>> u = W([Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)])
>>> v = W([Integer(0),Integer(1),Integer(0),Integer(2)])
>>> u.longest_common_prefix(v)
word: 010
>>> v.longest_common_prefix(u)
word: 010

Sage Live

W = Words([0,1,2])
W([0,1,0,2]).longest_common_prefix([0,1])
u = W([0,1,0,0,1])
v = W([0,1,0,2])
u.longest_common_prefix(v)
v.longest_common_prefix(u)

Using infinite words is also possible (and the return type is also a of the same type as self):

Sage

sage: W([0,1,0,0]).longest_common_prefix(words.FibonacciWord())
word: 0100
sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_char'>

Python

>>> from sage.all import *
>>> W([Integer(0),Integer(1),Integer(0),Integer(0)]).longest_common_prefix(words.FibonacciWord())
word: 0100
>>> type(_)
<class 'sage.combinat.words.word.FiniteWord_char'>

Sage Live

W([0,1,0,0]).longest_common_prefix(words.FibonacciWord())
type(_)

An example of an intensive usage:

Sage

sage: W = Words([0,1])
sage: w = words.FibonacciWord()
sage: w = W(list(w[:5000]))
sage: L = [[len(w[n:].longest_common_prefix(w[n+fibonacci(i):]))            # needs sage.libs.pari
....:      for i in range(5,15)] for n in range(1,1000)]
sage: for n,l in enumerate(L):                                              # needs sage.libs.pari
....:     if l.count(0) > 4:
....:         print("{} {}".format(n+1,l))
375 [0, 13, 0, 34, 0, 89, 0, 233, 0, 233]
376 [0, 12, 0, 33, 0, 88, 0, 232, 0, 232]
608 [8, 0, 21, 0, 55, 0, 144, 0, 377, 0]
609 [7, 0, 20, 0, 54, 0, 143, 0, 376, 0]
985 [0, 13, 0, 34, 0, 89, 0, 233, 0, 610]
986 [0, 12, 0, 33, 0, 88, 0, 232, 0, 609]

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1)])
>>> w = words.FibonacciWord()
>>> w = W(list(w[:Integer(5000)]))
>>> L = [[len(w[n:].longest_common_prefix(w[n+fibonacci(i):]))            # needs sage.libs.pari
...      for i in range(Integer(5),Integer(15))] for n in range(Integer(1),Integer(1000))]
>>> for n,l in enumerate(L):                                              # needs sage.libs.pari
...     if l.count(Integer(0)) > Integer(4):
...         print("{} {}".format(n+Integer(1),l))
375 [0, 13, 0, 34, 0, 89, 0, 233, 0, 233]
376 [0, 12, 0, 33, 0, 88, 0, 232, 0, 232]
608 [8, 0, 21, 0, 55, 0, 144, 0, 377, 0]
609 [7, 0, 20, 0, 54, 0, 143, 0, 376, 0]
985 [0, 13, 0, 34, 0, 89, 0, 233, 0, 610]
986 [0, 12, 0, 33, 0, 88, 0, 232, 0, 609]

Sage Live

W = Words([0,1])
w = words.FibonacciWord()
w = W(list(w[:5000]))
L = [[len(w[n:].longest_common_prefix(w[n+fibonacci(i):]))            # needs sage.libs.pari
     for i in range(5,15)] for n in range(1,1000)]
for n,l in enumerate(L):                                              # needs sage.libs.pari
    if l.count(0) > 4:
        print("{} {}".format(n+1,l))

longest_common_suffix(other)[source]¶

Return the longest common suffix between this word and other.

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: W([0,1,0,2]).longest_common_suffix([2,0,2])
word: 02
sage: u = W([0,1,0,0,1])
sage: v = W([1,2,0,0,1])
sage: u.longest_common_suffix(v)
word: 001
sage: v.longest_common_suffix(u)
word: 001

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> W([Integer(0),Integer(1),Integer(0),Integer(2)]).longest_common_suffix([Integer(2),Integer(0),Integer(2)])
word: 02
>>> u = W([Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)])
>>> v = W([Integer(1),Integer(2),Integer(0),Integer(0),Integer(1)])
>>> u.longest_common_suffix(v)
word: 001
>>> v.longest_common_suffix(u)
word: 001

Sage Live

W = Words([0,1,2])
W([0,1,0,2]).longest_common_suffix([2,0,2])
u = W([0,1,0,0,1])
v = W([1,2,0,0,1])
u.longest_common_suffix(v)
v.longest_common_suffix(u)

sage.combinat.words.word_char.reversed_word_iterator(w)[source]¶

This function exists only because it is not possible to use yield in the special method __reversed__.

EXAMPLES:

Sage

sage: W = Words([0,1,2])
sage: w = W([0,1,0,0,1,2])
sage: list(reversed(w)) # indirect doctest
[2, 1, 0, 0, 1, 0]

Python

>>> from sage.all import *
>>> W = Words([Integer(0),Integer(1),Integer(2)])
>>> w = W([Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(2)])
>>> list(reversed(w)) # indirect doctest
[2, 1, 0, 0, 1, 0]

Sage Live

W = Words([0,1,2])
w = W([0,1,0,0,1,2])
list(reversed(w)) # indirect doctest