This module implements word paths, which is an application of Combinatorics on Words to Discrete Geometry. A word path is the representation of a word as a discrete path in a vector space using a one-to-one correspondence between the alphabet and a set of vectors called steps. Many problems surrounding 2d lattice polygons (such as questions of self-intersection, area, inertia moment, etc.) can be solved in linear time (linear in the length of the perimeter) using theory from Combinatorics on Words.
On the square grid, the encoding of a path using a four-letter alphabet (for East, North, West and South directions) is also known as the Freeman chain code [1,2] (see [3] for further reading).
AUTHORS:
EXAMPLES:
The combinatorial class of all paths defined over three given steps:
sage: P = WordPaths('abc', steps=[(1,2), (-3,4), (0,-3)]); P
Word Paths over 3 steps
This defines a one-to-one correspondence between alphabet and steps:
sage: d = P.letters_to_steps()
sage: sorted(d.items())
[('a', (1, 2)), ('b', (-3, 4)), ('c', (0, -3))]
Creation of a path from the combinatorial class P defined above:
sage: p = P('abaccba'); p
Path: abaccba
Many functions can be used on p: the coordinates of its trajectory, ask whether p is a closed path, plot it and many other:
sage: list(p.points())
[(0, 0), (1, 2), (-2, 6), (-1, 8), (-1, 5), (-1, 2), (-4, 6), (-3, 8)]
sage: p.is_closed()
False
sage: p.plot()
Graphics object consisting of 3 graphics primitives
To obtain a list of all the available word path specific functions, use help(p):
sage: help(p)
Help on FiniteWordPath_2d_str in module sage.combinat.words.paths object:
...
Methods inherited from FiniteWordPath_2d:
...
Methods inherited from FiniteWordPath_all:
...
This only works on Python classes that derive from SageObject.
Since p is a finite word, many functions from the word library are available:
sage: p.crochemore_factorization()
(a, b, a, c, c, ba)
sage: p.is_palindrome()
False
sage: p[:3]
Path: aba
sage: len(p)
7
P also herits many functions from Words:
sage: P = WordPaths('rs', steps=[(1,2), (-1,4)]); P
Word Paths over 2 steps
sage: P.alphabet()
{'r', 's'}
sage: list(P.iterate_by_length(3))
[Path: rrr,
Path: rrs,
Path: rsr,
Path: rss,
Path: srr,
Path: srs,
Path: ssr,
Path: sss]
When the number of given steps is half the size of alphabet, the opposite of vectors are used:
sage: P = WordPaths('abcd', [(1,0), (0,1)])
sage: sorted(P.letters_to_steps().items())
[('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))]
Some built-in combinatorial classes of paths:
sage: P = WordPaths('abAB', steps='square_grid'); P
Word Paths on the square grid
sage: D = WordPaths('()', steps='dyck'); D
Finite Dyck paths
sage: d = D('()()()(())'); d
Path: ()()()(())
sage: d.plot()
Graphics object consisting of 3 graphics primitives
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: p = P('babaddefadabcadefaadfafabacdefa')
sage: p.plot()
Graphics object consisting of 3 graphics primitives
Vector steps may be in more than 2 dimensions:
sage: d = [(1,0,0), (0,1,0), (0,0,1)]
sage: P = WordPaths(alphabet='abc', steps=d); P
Word Paths over 3 steps
sage: p = P('abcabcabcabcaabacabcababcacbabacacabcaccbcac')
sage: p.plot()
Graphics3d Object
sage: d = [(1,3,5,1), (-5,1,-6,0), (0,0,1,9), (4,2,-1,0)]
sage: P = WordPaths(alphabet='rstu', steps=d); P
Word Paths over 4 steps
sage: p = P('rtusuusususuturrsust'); p
Path: rtusuusususuturrsust
sage: p.end_point()
(5, 31, -26, 30)
sage: CubePaths = WordPaths('abcABC', steps='cube_grid'); CubePaths
Word Paths on the cube grid
sage: CubePaths('abcabaabcabAAAAA').plot()
Graphics3d Object
The input data may be a str, a list, a tuple, a callable or a finite iterator:
sage: P = WordPaths([0, 1, 2, 3])
sage: P([0,1,2,3,2,1,2,3,2])
Path: 012321232
sage: P((0,1,2,3,2,1,2,3,2))
Path: 012321232
sage: P(lambda n:n%4, length=10)
Path: 0123012301
sage: P(iter([0,3,2,1]), length='finite')
Path: 0321
REFERENCES:
Bases: sage.combinat.words.paths.FiniteWordPath_all
x.__init__(...) initializes x; see help(type(x)) for signature
Returns an animation object illustrating the path growing step by step.
EXAMPLES:
sage: P = WordPaths('abAB')
sage: p = P('aaababbb')
sage: a = p.animate(); a
Animation with 9 frames
sage: show(a) # optional -- ImageMagick
sage: a.gif(delay=35, iterations=3) # optional
sage: P = WordPaths('abcdef',steps='triangle')
sage: p = P('abcdef')
sage: p.animate()
Animation with 8 frames
If the path is closed, the plain polygon is added at the end of the animation:
sage: P = WordPaths('abAB')
sage: p = P('ababAbABABaB')
sage: a = p.animate(); a
Animation with 14 frames
Another example illustrating a Fibonacci tile:
sage: w = words.fibonacci_tile(2)
sage: show(w.animate()) # optional
The first 4 Fibonacci tiles in an animation:
sage: a = words.fibonacci_tile(0).animate()
sage: b = words.fibonacci_tile(1).animate()
sage: c = words.fibonacci_tile(2).animate()
sage: d = words.fibonacci_tile(3).animate()
sage: (a*b*c*d).show() # optional
Note
If ImageMagick is not installed, you will get an error message like this:
/usr/local/share/sage/local/bin/sage-native-execute: 8: convert:
not found
Error: ImageMagick does not appear to be installed. Saving an
animation to a GIF file or displaying an animation requires
ImageMagick, so please install it and try again.
See www.imagemagick.org, for example.
Returns the area of a closed path.
INPUT:
EXAMPLES:
sage: P = WordPaths('abcd',steps=[(1,1),(-1,1),(-1,-1),(1,-1)])
sage: p = P('abcd')
sage: p.area() #todo: not implemented
2
Returns the height of self.
The height of a -path is merely the difference
between the highest and the lowest
-coordinate of each
points traced by it.
OUTPUT:
non negative real number
EXAMPLES:
sage: Freeman = WordPaths('abAB')
sage: Freeman('aababaabbbAA').height()
5
The function is well-defined if self is not simple or close:
sage: Freeman('aabAAB').height()
1
sage: Freeman('abbABa').height()
2
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,0),(1,1)])
sage: p = Paths('abbaa')
sage: p.height()
2
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.height()
2
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.height()
2.59807621135332
Returns a 2d Graphics illustrating the path.
INPUT:
EXAMPLES:
A non closed path on the square grid:
sage: P = WordPaths('abAB')
sage: P('abababAABAB').plot()
Graphics object consisting of 3 graphics primitives
A closed path on the square grid:
sage: P('abababAABABB').plot()
Graphics object consisting of 4 graphics primitives
A dyck path:
sage: P = WordPaths('()', steps='dyck')
sage: P('()()()((()))').plot()
Graphics object consisting of 3 graphics primitives
A path in the triangle grid:
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: P('abcdedededefab').plot()
Graphics object consisting of 3 graphics primitives
A polygon of length 220 that tiles the plane in two ways:
sage: P = WordPaths('abAB')
sage: P('aBababAbabaBaBABaBabaBaBABAbABABaBabaBaBABaBababAbabaBaBABaBabaBaBABAbABABaBABAbAbabAbABABaBABAbABABaBabaBaBABAbABABaBABAbAbabAbABAbAbabaBababAbABAbAbabAbABABaBABAbAbabAbABAbAbabaBababAbabaBaBABaBababAbabaBababAbABAbAbab').plot()
Graphics object consisting of 4 graphics primitives
With gridlines:
sage: P('ababababab').plot(gridlines=True)
TESTS:
sage: P = WordPaths('abAB')
sage: P().plot()
Graphics object consisting of 3 graphics primitives
sage: sum(map(plot,map(P,['a','A','b','B'])))
Graphics object consisting of 12 graphics primitives
Returns an arrow 2d graphics that goes from the start of the path to the end.
INPUT:
EXAMPLES:
sage: P = WordPaths('abcd'); P
Word Paths on the square grid
sage: p = P('aaaccaccacacacaccccccbbdd'); p
Path: aaaccaccacacacaccccccbbdd
sage: R = p.plot() + p.plot_directive_vector()
sage: show(R, axes=False, aspect_ratio=1)
TESTS:
A closed path:
sage: P('acbd').plot_directive_vector()
Graphics object consisting of 0 graphics primitives
Returns the width of self.
The height of a -path is merely the difference
between the rightmost and the leftmost
-coordinate of each
points traced by it.
OUTPUT:
non negative real number
EXAMPLES:
sage: Freeman = WordPaths('abAB')
sage: Freeman('aababaabbbAA').width()
5
The function is well-defined if self is not simple or close:
sage: Freeman('aabAAB').width()
2
sage: Freeman('abbABa').width()
1
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,0),(1,1)])
sage: p = Paths('abbaa')
sage: p.width()
5
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.width()
6
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.width()
4.50000000000000
Returns the maximum of the x-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.xmax()
3
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.xmax()
1
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.xmax()
6
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.xmax()
4.50000000000000
Returns the minimum of the x-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.xmin()
0
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,0),(-1,1)])
sage: p = Paths('abbba')
sage: p.xmin()
-2
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.xmin()
0
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.xmin()
0.000000000000000
Returns the maximum of the y-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.ymax()
3
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.ymax()
0
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.ymax()
2
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.ymax()
2.59807621135332
Returns the minimum of the y-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.ymin()
0
This works for any -paths:
sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.ymin()
-1
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.ymin()
0
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.ymin()
0.000000000000000
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2),(3,4)])
sage: p = P(['a','b','a']);p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_2d_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2),(3,4)])
sage: p = P('aba'); p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_2d_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_2d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2),(3,4)])
sage: p = P(('a','b','a'));p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_2d_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_all
x.__init__(...) initializes x; see help(type(x)) for signature
INPUT:
pathoptions - (dict, default:dict(rgbcolor=’red’,arrow_head=True, thickness=3)), options for the path drawing
startpoint - (boolean, default: True), draw the start point?
options for the start point drawing
EXAMPLES:
sage: d = ( vector((1,3,2)), vector((2,-4,5)) )
sage: P = WordPaths(alphabet='ab', steps=d); P
Word Paths over 2 steps
sage: p = P('ababab'); p
Path: ababab
sage: p.plot()
Graphics3d Object
sage: P = WordPaths('abcABC', steps='cube_grid')
sage: p = P('abcabcAABBC')
sage: p.plot()
Graphics3d Object
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2,0),(3,4,0)])
sage: p = P(['a','b','a']);p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_3d_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2,0),(3,4,0)])
sage: p = P('aba'); p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_3d_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_3d, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2,0),(3,4,0)])
sage: p = P(('a','b','a'));p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_3d_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.structure.sage_object.SageObject
x.__init__(...) initializes x; see help(type(x)) for signature
Returns the directive vector of self.
The directive vector is the vector starting at the start point and ending at the end point of the path self.
EXAMPLES:
sage: WordPaths('abcdef')('abababab').directive_vector()
(6, 2*sqrt3)
sage: WordPaths('abAB')('abababab').directive_vector()
(4, 4)
sage: P = WordPaths('abcABC', steps='cube_grid')
sage: P('ababababCC').directive_vector()
(4, 4, -2)
sage: WordPaths('abcdef')('abcdef').directive_vector()
(0, 0)
sage: P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
sage: P('abcabababacaacccbbcac').directive_vector()
(-16, 254, 63, 128)
Returns the end point of the path.
EXAMPLES:
sage: WordPaths('abcdef')('abababab').end_point()
(6, 2*sqrt3)
sage: WordPaths('abAB')('abababab').end_point()
(4, 4)
sage: P = WordPaths('abcABC', steps='cube_grid')
sage: P('ababababCC').end_point()
(4, 4, -2)
sage: WordPaths('abcdef')('abcdef').end_point()
(0, 0)
sage: P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
sage: P('abcabababacaacccbbcac').end_point()
(-16, 254, 63, 128)
Returns True if the path is closed, i.e. if the origin and the end of the path are equal.
EXAMPLES:
sage: P = WordPaths('abcd', steps=[(1,0),(0,1),(-1,0),(0,-1)])
sage: P('abcd').is_closed()
True
sage: P('abc').is_closed()
False
sage: P().is_closed()
True
sage: P('aacacc').is_closed()
True
Returns True if the path is simple, i.e. if all its points are distincts.
If the path is closed, the last point is not considered.
EXAMPLES:
sage: P = WordPaths('abcdef',steps='triangle_grid');P
Word Paths on the triangle grid
sage: P('abc').is_simple()
True
sage: P('abcde').is_simple()
True
sage: P('abcdef').is_simple()
True
sage: P('ad').is_simple()
True
sage: P('aabdee').is_simple()
False
The is_tangent() method, which is implemented for words, has an extended meaning for word paths, which is not implemented yet.
TESTS:
sage: WordPaths('ab')('abbab').is_tangent()
Traceback (most recent call last):
...
NotImplementedError
AUTHOR:
Return an image of the projection of the successive points of the path into the space orthogonal to the given vector.
INPUT:
OUTPUT:
2d or 3d Graphic object.
EXAMPLES:
The Rauzy fractal:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:200])
sage: w.plot_projection(v) # optional long time (2 s)
In this case, the abelianized vector doesn’t give a good projection:
sage: w.plot_projection() # optional long time (2 s)
You can project only the letters you want:
sage: w.plot_projection(v, letters='12') # optional long time (2 s)
You can increase or decrease the precision of the computations by changing the ring of the projection matrix:
sage: w.plot_projection(v, ring=RealField(20)) # optional long time (2 s)
You can change the size of the points:
sage: w.plot_projection(v, size=30) # optional long time (2 s)
You can assign the color of a letter to the projected prefix to the right or the left of the letter:
sage: w.plot_projection(v, kind='left') # optional long time (2 s)
To remove the axis, do like this:
sage: r = w.plot_projection(v)
sage: r.axes(False)
sage: r # optional long time (2 s)
You can assign different colors to each letter:
sage: color = {'1':'purple', '2':(.2,.3,.4), '3': 'magenta'}
sage: w.plot_projection(v, color=color) # optional long time (2 s)
The 3d-Rauzy fractal:
sage: s = WordMorphism('1->12,2->13,3->14,4->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('1234',[(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)])
sage: w = P(D[:200])
sage: w.plot_projection(v) # optional long time (1 s)
The dimension of vector space of the parent must be 3 or 4:
sage: P = WordPaths('ab', [(1, 0), (0, 1)])
sage: p = P('aabbabbab')
sage: p.plot_projection()
Traceback (most recent call last):
...
TypeError: The dimension of the vector space (=2) must be 3 or 4
Returns an iterator yielding a list of points used to draw the path represented by this word.
INPUT:
EXAMPLES:
A simple closed square:
sage: P = WordPaths('abAB')
sage: list(P('abAB').points())
[(0, 0), (1, 0), (1, 1), (0, 1), (0, 0)]
A simple closed square without the last point:
sage: list(P('abAB').points(include_last=False))
[(0, 0), (1, 0), (1, 1), (0, 1)]
sage: list(P('abaB').points())
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 0)]
Return the path projected into the space orthogonal to the given vector.
INPUT:
OUTPUT:
word path
EXAMPLES:
The projected path of the tribonacci word:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:1000])
sage: p = w.projected_path(v)
sage: p
Path: 1213121121312121312112131213121121312121...
sage: p[:20].plot()
Graphics object consisting of 3 graphics primitives
The ring argument allows to change the precision of the projected steps:
sage: p = w.projected_path(v, RealField(10))
sage: p
Path: 1213121121312121312112131213121121312121...
sage: p.parent().letters_to_steps()
{'1': (-0.53, 0.00), '2': (0.75, -0.48), '3': (0.41, 0.88)}
Return an iterator of the projection of the orbit points of the path into the space orthogonal to the given vector.
INPUT:
OUTPUT:
iterator of points
EXAMPLES:
Projected points of the Rauzy fractal:
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:200])
sage: it = w.projected_point_iterator(v)
sage: for i in range(6): it.next()
(0.000000000000000, 0.000000000000000)
(-0.526233343362516, 0.000000000000000)
(0.220830337618112, -0.477656250512816)
(-0.305403005744404, -0.477656250512816)
(0.100767309386062, 0.400890564600664)
(-0.425466033976454, 0.400890564600664)
Projected points of a 2d path:
sage: P = WordPaths('ab','ne')
sage: p = P('aabbabbab')
sage: it = p.projected_point_iterator(ring=RealField(20))
sage: for i in range(8): it.next()
(0.00000)
(0.78087)
(1.5617)
(0.93704)
(0.31235)
(1.0932)
(0.46852)
(-0.15617)
Return the starting point of self.
OUTPUT:
vector
EXAMPLES:
sage: WordPaths('abcdef')('abcdef').start_point()
(0, 0)
sage: WordPaths('abcdef', steps='cube_grid')('abcdef').start_point()
(0, 0, 0)
sage: P = WordPaths('ab', steps=[(1,0,0,0),(0,1,0,0)])
sage: P('abbba').start_point()
(0, 0, 0, 0)
Returns the trajectory of self as a tikz str.
EXAMPLES:
sage: P = WordPaths('abcdef')
sage: p = P('abcde')
sage: p.tikz_trajectory()
'(0.000, 0.000) -- (1.00, 0.000) -- (1.50, 0.866) -- (1.00, 1.73) -- (0.000, 1.73) -- (-0.500, 0.866)'
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths(['a','b'],[(1,2,0,0),(3,4,0,0)])
sage: p = P(['a','b','a']);p
Path: aba
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_all_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab',[(1,2,0,0),(3,4,0,0)])
sage: p = P('aabbb'); p
Path: aabbb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_all_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_all, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab',[(1,2,0,0),(3,4,0,0)])
sage: p = P( ('a','b','b') ); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_all_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_3d
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='cube')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_cube_grid_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='cube')
sage: p = P('abb'); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_cube_grid_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_cube_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='cube')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_cube_grid_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_2d
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='dyck')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_dyck_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='dyck')
sage: p = P('abb'); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_dyck_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_dyck, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='dyck')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_dyck_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_triangle_grid
INPUT:
EXAMPLES:
sage: F = WordPaths('abcdef', steps='hexagon'); F
Word Paths on the hexagonal grid
sage: f = F('aaabbbccddef'); f
Path: aaabbbccddef
sage: f == loads(dumps(f))
True
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='hexagon')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='hexagon')
sage: p = P('abb'); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_hexagonal_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='hexagon')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_2d
x.__init__(...) initializes x; see help(type(x)) for signature
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='ne')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_north_east_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='ne')
sage: p = P('abb'); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_north_east_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_north_east, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('ab', steps='ne')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_north_east_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_2d
x.__init__(...) initializes x; see help(type(x)) for signature
Returns the area of a closed path.
INPUT:
EXAMPLES:
sage: P = WordPaths('abAB', steps='square_grid')
sage: P('abAB').area()
1
sage: P('aabbAABB').area()
4
sage: P('aabbABAB').area()
3
The area of the Fibonacci tiles:
sage: [words.fibonacci_tile(i).area() for i in range(6)]
[1, 5, 29, 169, 985, 5741]
sage: [words.dual_fibonacci_tile(i).area() for i in range(6)]
[1, 5, 29, 169, 985, 5741]
sage: oeis(_)[0] # optional -- internet
A001653: Numbers n such that 2*n^2 - 1 is a square.
sage: _.first_terms() # optional -- internet
(1,
5,
29,
169,
985,
5741,
33461,
195025,
1136689,
6625109,
38613965,
225058681,
1311738121,
7645370045,
44560482149,
259717522849,
1513744654945,
8822750406821,
51422757785981,
299713796309065,
1746860020068409)
TESTS:
sage: P = WordPaths('abAB', steps='square_grid')
sage: P('a').area()
Traceback (most recent call last):
...
TypeError: the path must be closed to compute its area
Returns True if self represents a closed path and False otherwise.
EXAMPLES:
sage: P = WordPaths('abAB', steps='square_grid')
sage: P('aA').is_closed()
True
sage: P('abAB').is_closed()
True
sage: P('ababAABB').is_closed()
True
sage: P('aaabbbAABB').is_closed()
False
sage: P('ab').is_closed()
False
Returns True if the path is simple, i.e. if all its points are distincts.
If the path is closed, the last point is not considered.
Note
The linear algorithm described in the thesis of Xavier Provençal should be implemented here.
EXAMPLES:
sage: P = WordPaths('abAB', steps='square_grid')
sage: P('abab').is_simple()
True
sage: P('abAB').is_simple()
True
sage: P('abA').is_simple()
True
sage: P('aabABB').is_simple()
False
sage: P().is_simple()
True
sage: P('A').is_simple()
True
sage: P('aA').is_simple()
True
sage: P('aaA').is_simple()
False
REFERENCES:
Returns the trajectory of self as a tikz str.
EXAMPLES:
sage: f = words.fibonacci_tile(1)
sage: f.tikz_trajectory()
'(0, 0) -- (0, -1) -- (-1, -1) -- (-1, -2) -- (0, -2) -- (0, -3) -- (1, -3) -- (1, -2) -- (2, -2) -- (2, -1) -- (1, -1) -- (1, 0) -- (0, 0)'
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcd', steps='square')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcd', steps='square')
sage: p = P('abccc'); p
Path: abccc
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_square_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcd', steps='square')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_tuple'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.paths.FiniteWordPath_2d
x.__init__(...) initializes x; see help(type(x)) for signature
Returns the maximum of the x-coordinates of the path.
EXAMPLES:
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.xmax()
4.50000000000000
sage: w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC')
sage: w.xmax()
4.00000000000000
Returns the minimum of the x-coordinates of the path.
EXAMPLES:
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.xmin()
0.000000000000000
sage: w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC')
sage: w.xmin()
-3.00000000000000
Returns the maximum of the y-coordinates of the path.
EXAMPLES:
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.ymax()
2.59807621135332
sage: w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC')
sage: w.ymax()
8.66025403784439
Returns the minimum of the y-coordinates of the path.
EXAMPLES:
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')
sage: w.ymin()
0.000000000000000
sage: w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC')
sage: w.ymin()
-0.866025403784439
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=False); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: w.length()
9
sage: w = Word(f, caching=False); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: w.length() is None
False
sage: w.length()
+Infinity
TESTS:
sage: from sage.combinat.words.word_infinite_datatypes import WordDatatype_callable
sage: WordDatatype_callable(Words(),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
sage: WordDatatype_callable(Words([0,1,2]),lambda n:n%3)
<sage.combinat.words.word_infinite_datatypes.WordDatatype_callable object at ...>
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: f = lambda n : 'x' if n % 2 == 0 else 'y'
sage: w = Word(f, length=9, caching=True); w
word: xyxyxyxyx
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: w.length()
9
sage: w = Word(f, caching=True); w
word: xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy...
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: w.length() is None
False
sage: w.length()
+Infinity
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: w = Word(iter("abbabaab"), length="unknown", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length() is None
False
sage: w.length()
8
sage: s = "abbabaabbaababbabaababbaabbabaabbaababbaabbabaabab"
sage: w = Word(iter(s), length="unknown", caching=False); w
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: w.length() is None
True
sage: w = Word(iter("abbabaab"), length="finite", caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8, caching=False); w
word: abbabaab
sage: isinstance(w, sage.combinat.words.word_infinite_datatypes.WordDatatype_iter)
True
sage: w.length()
8
Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
INPUT:
EXAMPLES:
sage: import itertools
sage: Word(itertools.cycle("abbabaab"))
word: abbabaababbabaababbabaababbabaababbabaab...
sage: w = Word(iter("abbabaab"), length="finite"); w
word: abbabaab
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length="unknown"); w
word: abbabaab
sage: w.length()
8
sage: list(w)
['a', 'b', 'b', 'a', 'b', 'a', 'a', 'b']
sage: w.length()
8
sage: w = Word(iter("abbabaab"), length=8)
sage: w._len
8
Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='triangle')
sage: p = P(['a','b','b']); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_triangle_grid_list'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='triangle')
sage: p = P('abb'); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_triangle_grid_str'>
sage: p == loads(dumps(p))
True
Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.paths.FiniteWordPath_triangle_grid, sage.combinat.words.finite_word.FiniteWord_class
TESTS:
sage: P = WordPaths('abcdef', steps='triangle')
sage: p = P(('a','b','b')); p
Path: abb
sage: type(p)
<class 'sage.combinat.words.paths.FiniteWordPath_triangle_grid_tuple'>
sage: p == loads(dumps(p))
True
Returns the combinatorial class of paths of the given type of steps.
INPUT:
OUTPUT:
EXAMPLES:
The steps can be given explicitely:
sage: WordPaths('abc', steps=[(1,2), (-1,4), (0,-3)])
Word Paths over 3 steps
Different type of input alphabet:
sage: WordPaths(range(3), steps=[(1,2), (-1,4), (0,-3)])
Word Paths over 3 steps
sage: WordPaths(['cric','crac','croc'], steps=[(1,2), (1,4), (0,3)])
Word Paths over 3 steps
Directions can be in three dimensions as well:
sage: WordPaths('ab', steps=[(1,2,2),(-1,4,2)])
Word Paths over 2 steps
When the number of given steps is half the size of alphabet, the opposite of vectors are used:
sage: P = WordPaths('abcd', [(1,0), (0,1)])
sage: P
Word Paths over 4 steps
sage: sorted(P.letters_to_steps().items())
[('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))]
When no steps are given, default classes are returned:
sage: WordPaths('ab')
Word Paths in North and East steps
sage: WordPaths(range(4))
Word Paths on the square grid
sage: WordPaths(range(6))
Word Paths on the hexagonal grid
There are many type of built-in steps...
On a two letters alphabet:
sage: WordPaths('ab', steps='north_east')
Word Paths in North and East steps
sage: WordPaths('()', steps='dyck')
Finite Dyck paths
On a four letters alphabet:
sage: WordPaths('ruld', steps='square_grid')
Word Paths on the square grid
On a six letters alphabet:
sage: WordPaths('abcdef', steps='hexagonal_grid')
Word Paths on the hexagonal grid
sage: WordPaths('abcdef', steps='triangle_grid')
Word Paths on the triangle grid
sage: WordPaths('abcdef', steps='cube_grid')
Word Paths on the cube grid
TESTS:
sage: WordPaths(range(5))
Traceback (most recent call last):
...
TypeError: Unable to make a class WordPaths from {0, 1, 2, 3, 4}
sage: WordPaths('abAB', steps='square_gridd')
Traceback (most recent call last):
...
TypeError: Unknown type of steps : square_gridd
Bases: sage.combinat.words.words.Words_over_OrderedAlphabet
The combinatorial class of all paths, i.e of all words over an alphabet where each letter is mapped to a step (a vector).
Returns the dictionary mapping letters to vectors (steps).
EXAMPLES:
sage: d = WordPaths('ab').letters_to_steps()
sage: sorted(d.items())
[('a', (0, 1)), ('b', (1, 0))]
sage: d = WordPaths('abcd').letters_to_steps()
sage: sorted(d.items())
[('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))]
sage: d = WordPaths('abcdef').letters_to_steps()
sage: sorted(d.items())
[('a', (1, 0)),
('b', (1/2, 1/2*sqrt3)),
('c', (-1/2, 1/2*sqrt3)),
('d', (-1, 0)),
('e', (-1/2, -1/2*sqrt3)),
('f', (1/2, -1/2*sqrt3))]
Return the vector space over which the steps of the paths are defined.
EXAMPLES:
sage: WordPaths('ab',steps='dyck').vector_space()
Ambient free module of rank 2 over the principal ideal domain Integer Ring
sage: WordPaths('ab',steps='north_east').vector_space()
Ambient free module of rank 2 over the principal ideal domain Integer Ring
sage: WordPaths('abcd',steps='square_grid').vector_space()
Ambient free module of rank 2 over the principal ideal domain Integer Ring
sage: WordPaths('abcdef',steps='hexagonal_grid').vector_space()
Vector space of dimension 2 over Number Field in sqrt3 with defining polynomial x^2 - 3
sage: WordPaths('abcdef',steps='cube_grid').vector_space()
Ambient free module of rank 3 over the principal ideal domain Integer Ring
sage: WordPaths('abcdef',steps='triangle_grid').vector_space()
Vector space of dimension 2 over Number Field in sqrt3 with defining polynomial x^2 - 3
Bases: sage.combinat.words.paths.WordPaths_all
The combinatorial class of all paths on the cube grid.
Bases: sage.combinat.words.paths.WordPaths_all
The combinatorial class of all dyck paths.
Bases: sage.combinat.words.paths.WordPaths_triangle_grid
The combinatorial class of all paths on the hexagonal grid.
Bases: sage.combinat.words.paths.WordPaths_all
The combinatorial class of all paths using North and East directions.
Bases: sage.combinat.words.paths.WordPaths_all
The combinatorial class of all paths on the square grid.
Bases: sage.combinat.words.paths.WordPaths_all
The combinatorial class of all paths on the triangle grid.