Word paths¶
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:
Arnaud Bergeron (2008) : Initial version, path on the square grid
Sébastien Labbé (2009-01-14) : New classes and hierarchy, doc and functions.
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
>>> from sage.all import *
>>> P = WordPaths('abc', steps=[(Integer(1),Integer(2)), (-Integer(3),Integer(4)), (Integer(0),-Integer(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))]
>>> from sage.all import *
>>> d = P.letters_to_steps()
>>> 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
>>> from sage.all import *
>>> 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() # needs sage.plot
Graphics object consisting of 3 graphics primitives
>>> from sage.all import *
>>> list(p.points())
[(0, 0), (1, 2), (-2, 6), (-1, 8), (-1, 5), (-1, 2), (-4, 6), (-3, 8)]
>>> p.is_closed()
False
>>> p.plot() # needs sage.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:
...
>>> from sage.all import *
>>> help(p)
Help on FiniteWordPath_2d_str in module sage.combinat.words.paths object:
...
Methods inherited from FiniteWordPath_2d:
...
Methods inherited from FiniteWordPath_all:
...
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
>>> from sage.all import *
>>> p.crochemore_factorization()
(a, b, a, c, c, ba)
>>> p.is_palindrome()
False
>>> p[:Integer(3)]
Path: aba
>>> 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]
>>> from sage.all import *
>>> P = WordPaths('rs', steps=[(Integer(1),Integer(2)), (-Integer(1),Integer(4))]); P
Word Paths over 2 steps
>>> P.alphabet()
{'r', 's'}
>>> list(P.iterate_by_length(Integer(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))]
>>> from sage.all import *
>>> P = WordPaths('abcd', [(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> 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
>>> from sage.all import *
>>> 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() # needs sage.plot
Graphics object consisting of 3 graphics primitives
>>> from sage.all import *
>>> D = WordPaths('()', steps='dyck'); D
Finite Dyck paths
>>> d = D('()()()(())'); d
Path: ()()()(())
>>> d.plot() # needs sage.plot
Graphics object consisting of 3 graphics primitives
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: p = P('babaddefadabcadefaadfafabacdefa')
sage: p.plot() # needs sage.plot
Graphics object consisting of 3 graphics primitives
>>> from sage.all import *
>>> P = WordPaths('abcdef', steps='triangle_grid')
>>> p = P('babaddefadabcadefaadfafabacdefa')
>>> p.plot() # needs sage.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() # needs sage.plot
Graphics3d Object
>>> from sage.all import *
>>> d = [(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))]
>>> P = WordPaths(alphabet='abc', steps=d); P
Word Paths over 3 steps
>>> p = P('abcabcabcabcaabacabcababcacbabacacabcaccbcac')
>>> p.plot() # needs sage.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)
>>> from sage.all import *
>>> d = [(Integer(1),Integer(3),Integer(5),Integer(1)), (-Integer(5),Integer(1),-Integer(6),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(9)), (Integer(4),Integer(2),-Integer(1),Integer(0))]
>>> P = WordPaths(alphabet='rstu', steps=d); P
Word Paths over 4 steps
>>> p = P('rtusuusususuturrsust'); p
Path: rtusuusususuturrsust
>>> 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() # needs sage.plot
Graphics3d Object
>>> from sage.all import *
>>> CubePaths = WordPaths('abcABC', steps='cube_grid'); CubePaths
Word Paths on the cube grid
>>> CubePaths('abcabaabcabAAAAA').plot() # needs sage.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
>>> from sage.all import *
>>> P = WordPaths([Integer(0), Integer(1), Integer(2), Integer(3)])
>>> P([Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2)])
Path: 012321232
>>> P((Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2)))
Path: 012321232
>>> P(lambda n:n%Integer(4), length=Integer(10))
Path: 0123012301
>>> P(iter([Integer(0),Integer(3),Integer(2),Integer(1)]), length='finite')
Path: 0321
REFERENCES:
[1] Freeman, H.: On the encoding of arbitrary geometric configurations. IRE Trans. Electronic Computer 10 (1961) 260-268.
[2] Freeman, H.: Boundary encoding and processing. In Lipkin, B., Rosenfeld, A., eds.: Picture Processing and Psychopictorics, Academic Press, New York (1970) 241-266.
[3] Braquelaire, J.P., Vialard, A.: Euclidean paths: A new representation of boundary of discrete regions. Graphical Models and Image Processing 61 (1999) 16-43.
- class sage.combinat.words.paths.FiniteWordPath_2d[source]¶
Bases:
FiniteWordPath_all
- animate()[source]¶
Return an animation object illustrating the path growing step by step.
EXAMPLES:
sage: P = WordPaths('abAB') sage: p = P('aaababbb') sage: a = p.animate(); print(a) # needs sage.plot Animation with 9 frames sage: show(a) # long time, optional - imagemagick, needs sage.plot sage: show(a, delay=35, iterations=3) # long time, optional - imagemagick, needs sage.plot
>>> from sage.all import * >>> P = WordPaths('abAB') >>> p = P('aaababbb') >>> a = p.animate(); print(a) # needs sage.plot Animation with 9 frames >>> show(a) # long time, optional - imagemagick, needs sage.plot >>> show(a, delay=Integer(35), iterations=Integer(3)) # long time, optional - imagemagick, needs sage.plot
sage: P = WordPaths('abcdef',steps='triangle') sage: p = P('abcdef') sage: a = p.animate(); print(a) # needs sage.plot Animation with 8 frames sage: show(a) # long time, optional - imagemagick, needs sage.plot
>>> from sage.all import * >>> P = WordPaths('abcdef',steps='triangle') >>> p = P('abcdef') >>> a = p.animate(); print(a) # needs sage.plot Animation with 8 frames >>> show(a) # long time, optional - imagemagick, needs sage.plot
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(); print(a) # needs sage.plot Animation with 14 frames sage: show(a) # long time, optional - imagemagick, needs sage.plot
>>> from sage.all import * >>> P = WordPaths('abAB') >>> p = P('ababAbABABaB') >>> a = p.animate(); print(a) # needs sage.plot Animation with 14 frames >>> show(a) # long time, optional - imagemagick, needs sage.plot
Another example illustrating a Fibonacci tile:
sage: w = words.fibonacci_tile(2) sage: a = w.animate(); print(a) # needs sage.plot Animation with 54 frames sage: show(a) # long time, optional - imagemagick, needs sage.plot
>>> from sage.all import * >>> w = words.fibonacci_tile(Integer(2)) >>> a = w.animate(); print(a) # needs sage.plot Animation with 54 frames >>> show(a) # long time, optional - imagemagick, needs sage.plot
The first 4 Fibonacci tiles in an animation:
sage: # needs sage.plot 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: print(a*b*c*d) Animation with 296 frames sage: show(a*b*c*d) # long time, optional - imagemagick
>>> from sage.all import * >>> # needs sage.plot >>> a = words.fibonacci_tile(Integer(0)).animate() >>> b = words.fibonacci_tile(Integer(1)).animate() >>> c = words.fibonacci_tile(Integer(2)).animate() >>> d = words.fibonacci_tile(Integer(3)).animate() >>> print(a*b*c*d) Animation with 296 frames >>> show(a*b*c*d) # long time, optional - imagemagick
Note
If ImageMagick is not installed, you will get an error message like this:
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.
- area()[source]¶
Return the area of a closed path.
INPUT:
self
– a closed path
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
>>> from sage.all import * >>> P = WordPaths('abcd',steps=[(Integer(1),Integer(1)),(-Integer(1),Integer(1)),(-Integer(1),-Integer(1)),(Integer(1),-Integer(1))]) >>> p = P('abcd') >>> p.area() #todo: not implemented 2
- height()[source]¶
Return the height of
self
.The height of a \(2d\)-path is merely the difference between the highest and the lowest \(y\)-coordinate of each points traced by it.
OUTPUT: nonnegative real number
EXAMPLES:
sage: Freeman = WordPaths('abAB') sage: Freeman('aababaabbbAA').height() 5
>>> from sage.all import * >>> Freeman = WordPaths('abAB') >>> 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
>>> from sage.all import * >>> Freeman('aabAAB').height() 1 >>> Freeman('abbABa').height() 2
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(1),Integer(1))]) >>> p = Paths('abbaa') >>> p.height() 2 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.height() 2 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.height() 2.59807621135332
- height_vector()[source]¶
Return the height at each point.
EXAMPLES:
sage: Paths = WordPaths('ab', steps=[(1,0),(0,1)]) sage: p = Paths('abbba') sage: p.height_vector() [0, 0, 1, 2, 3, 3]
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1))]) >>> p = Paths('abbba') >>> p.height_vector() [0, 0, 1, 2, 3, 3]
- plot(pathoptions={'rgbcolor': 'red', 'thickness': 3}, fill=True, filloptions={'rgbcolor': 'red', 'alpha': 0.2}, startpoint=True, startoptions={'rgbcolor': 'red', 'pointsize': 100}, endarrow=True, arrowoptions={'rgbcolor': 'red', 'arrowsize': 20, 'width': 3}, gridlines=False, gridoptions={})[source]¶
Return a 2d Graphics illustrating the path.
INPUT:
pathoptions
– (dict, default:dict(rgbcolor=’red’,thickness=3)), options for the path drawingfill
– boolean (default:True
); if fill isTrue
and if the path is closed, the inside is coloredfilloptions
– (dict, default:dict(rgbcolor=’red’,alpha=0.2)), options for the inside fillingstartpoint
– boolean (default:True
); draw the start point?startoptions
– (dict, default:dict(rgbcolor=’red’,pointsize=100)) options for the start point drawingendarrow
– boolean (default:True
); draw an arrow end at the end?arrowoptions
– (dict, default:dict(rgbcolor=’red’,arrowsize=20, width=3)) options for the end point arrowgridlines
– boolean (default:False
); show gridlines?gridoptions
– (dict, default: {}), options for the gridlines
EXAMPLES:
A non closed path on the square grid:
sage: P = WordPaths('abAB') sage: P('abababAABAB').plot() # needs sage.plot Graphics object consisting of 3 graphics primitives
>>> from sage.all import * >>> P = WordPaths('abAB') >>> P('abababAABAB').plot() # needs sage.plot Graphics object consisting of 3 graphics primitives
A closed path on the square grid:
sage: P('abababAABABB').plot() # needs sage.plot Graphics object consisting of 4 graphics primitives
>>> from sage.all import * >>> P('abababAABABB').plot() # needs sage.plot Graphics object consisting of 4 graphics primitives
A Dyck path:
sage: P = WordPaths('()', steps='dyck') sage: P('()()()((()))').plot() # needs sage.plot Graphics object consisting of 3 graphics primitives
>>> from sage.all import * >>> P = WordPaths('()', steps='dyck') >>> P('()()()((()))').plot() # needs sage.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() # needs sage.plot Graphics object consisting of 3 graphics primitives
>>> from sage.all import * >>> P = WordPaths('abcdef', steps='triangle_grid') >>> P('abcdedededefab').plot() # needs sage.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() # needs sage.plot Graphics object consisting of 4 graphics primitives
>>> from sage.all import * >>> P = WordPaths('abAB') >>> P('aBababAbabaBaBABaBabaBaBABAbABABaBabaBaBABaBababAbabaBaBABaBabaBaBABAbABABaBABAbAbabAbABABaBABAbABABaBabaBaBABAbABABaBABAbAbabAbABAbAbabaBababAbABAbAbabAbABABaBABAbAbabAbABAbAbabaBababAbabaBaBABaBababAbabaBababAbABAbAbab').plot() # needs sage.plot Graphics object consisting of 4 graphics primitives
With gridlines:
sage: P('ababababab').plot(gridlines=True) # needs sage.plot
>>> from sage.all import * >>> P('ababababab').plot(gridlines=True) # needs sage.plot
- plot_directive_vector(options={'rgbcolor': 'blue'})[source]¶
Return an arrow 2d graphics that goes from the start of the path to the end.
INPUT:
options
– dictionary, default: {‘rgbcolor’: ‘blue’} graphic options for the arrow
If the start is the same as the end, a single point is returned.
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() # needs sage.plot sage: R.axes(False) # needs sage.plot sage: R.set_aspect_ratio(1) # needs sage.plot sage: R.plot() # needs sage.plot Graphics object consisting of 4 graphics primitives
>>> from sage.all import * >>> P = WordPaths('abcd'); P Word Paths on the square grid >>> p = P('aaaccaccacacacaccccccbbdd'); p Path: aaaccaccacacacaccccccbbdd >>> R = p.plot() + p.plot_directive_vector() # needs sage.plot >>> R.axes(False) # needs sage.plot >>> R.set_aspect_ratio(Integer(1)) # needs sage.plot >>> R.plot() # needs sage.plot Graphics object consisting of 4 graphics primitives
- width()[source]¶
Return the width of
self
.The height of a \(2d\)-path is merely the difference between the rightmost and the leftmost \(x\)-coordinate of each points traced by it.
OUTPUT: nonnegative real number
EXAMPLES:
sage: Freeman = WordPaths('abAB') sage: Freeman('aababaabbbAA').width() 5
>>> from sage.all import * >>> Freeman = WordPaths('abAB') >>> 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
>>> from sage.all import * >>> Freeman('aabAAB').width() 2 >>> Freeman('abbABa').width() 1
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(1),Integer(1))]) >>> p = Paths('abbaa') >>> p.width() 5 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.width() 6 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.width() 4.50000000000000
- width_vector()[source]¶
Return the width at each point.
EXAMPLES:
sage: Paths = WordPaths('ab', steps=[(1,0),(0,1)]) sage: p = Paths('abbba') sage: p.width_vector() [0, 1, 1, 1, 1, 2]
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1))]) >>> p = Paths('abbba') >>> p.width_vector() [0, 1, 1, 1, 1, 2]
- xmax()[source]¶
Return the maximum of the x-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123') sage: p = P('0101013332') sage: p.xmax() 3
>>> from sage.all import * >>> P = WordPaths('0123') >>> p = P('0101013332') >>> p.xmax() 3
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))]) >>> p = Paths('ababa') >>> p.xmax() 1 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.xmax() 6 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.xmax() 4.50000000000000
- xmin()[source]¶
Return the minimum of the x-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123') sage: p = P('0101013332') sage: p.xmin() 0
>>> from sage.all import * >>> P = WordPaths('0123') >>> p = P('0101013332') >>> p.xmin() 0
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(-Integer(1),Integer(1))]) >>> p = Paths('abbba') >>> p.xmin() -2 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.xmin() 0 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.xmin() 0.000000000000000
- ymax()[source]¶
Return the maximum of the y-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123') sage: p = P('0101013332') sage: p.ymax() 3
>>> from sage.all import * >>> P = WordPaths('0123') >>> p = P('0101013332') >>> p.ymax() 3
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))]) >>> p = Paths('ababa') >>> p.ymax() 0 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.ymax() 2 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.ymax() 2.59807621135332
- ymin()[source]¶
Return the minimum of the y-coordinates of the path.
EXAMPLES:
sage: P = WordPaths('0123') sage: p = P('0101013332') sage: p.ymin() 0
>>> from sage.all import * >>> P = WordPaths('0123') >>> p = P('0101013332') >>> p.ymin() 0
This works for any \(2d\)-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
>>> from sage.all import * >>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))]) >>> p = Paths('ababa') >>> p.ymin() -1 >>> DyckPaths = WordPaths('ab', steps='dyck') >>> p = DyckPaths('abaabb') >>> p.ymin() 0 >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.ymin() 0.000000000000000
- class sage.combinat.words.paths.FiniteWordPath_2d_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_2d_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_2d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d[source]¶
Bases:
FiniteWordPath_all
- plot(pathoptions={'rgbcolor': 'red', 'arrow_head': True, 'thickness': 3}, startpoint=True, startoptions={'rgbcolor': 'red', 'size': 10})[source]¶
INPUT:
pathoptions
– (dict, default:dict(rgbcolor=’red’,arrow_head=True, thickness=3)), options for the path drawingstartpoint
– boolean (default:True
); draw the start point?startoptions
– (dict, default:dict(rgbcolor=’red’,size=10)) 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() # needs sage.plot Graphics3d Object sage: P = WordPaths('abcABC', steps='cube_grid') sage: p = P('abcabcAABBC') sage: p.plot() # needs sage.plot Graphics3d Object
>>> from sage.all import * >>> d = ( vector((Integer(1),Integer(3),Integer(2))), vector((Integer(2),-Integer(4),Integer(5))) ) >>> P = WordPaths(alphabet='ab', steps=d); P Word Paths over 2 steps >>> p = P('ababab'); p Path: ababab >>> p.plot() # needs sage.plot Graphics3d Object >>> P = WordPaths('abcABC', steps='cube_grid') >>> p = P('abcabcAABBC') >>> p.plot() # needs sage.plot Graphics3d Object
- class sage.combinat.words.paths.FiniteWordPath_3d_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_3d_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_3d
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all[source]¶
Bases:
SageObject
- directive_vector()[source]¶
Return 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)
>>> from sage.all import * >>> WordPaths('abcdef')('abababab').directive_vector() (6, 2*sqrt3) >>> WordPaths('abAB')('abababab').directive_vector() (4, 4) >>> P = WordPaths('abcABC', steps='cube_grid') >>> P('ababababCC').directive_vector() (4, 4, -2) >>> WordPaths('abcdef')('abcdef').directive_vector() (0, 0) >>> P = WordPaths('abc', steps=[(Integer(1),Integer(3),Integer(7),Integer(9)),(-Integer(4),Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(32),Integer(1),Integer(8))]) >>> P('abcabababacaacccbbcac').directive_vector() (-16, 254, 63, 128)
- end_point()[source]¶
Return 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)
>>> from sage.all import * >>> WordPaths('abcdef')('abababab').end_point() (6, 2*sqrt3) >>> WordPaths('abAB')('abababab').end_point() (4, 4) >>> P = WordPaths('abcABC', steps='cube_grid') >>> P('ababababCC').end_point() (4, 4, -2) >>> WordPaths('abcdef')('abcdef').end_point() (0, 0) >>> P = WordPaths('abc', steps=[(Integer(1),Integer(3),Integer(7),Integer(9)),(-Integer(4),Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(32),Integer(1),Integer(8))]) >>> P('abcabababacaacccbbcac').end_point() (-16, 254, 63, 128)
- is_closed()[source]¶
Return
True
if the path is closed.A path is closed 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
>>> from sage.all import * >>> P = WordPaths('abcd', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1)),(-Integer(1),Integer(0)),(Integer(0),-Integer(1))]) >>> P('abcd').is_closed() True >>> P('abc').is_closed() False >>> P().is_closed() True >>> P('aacacc').is_closed() True
- is_simple()[source]¶
Return
True
if the path is simple.A path is simple if all its points are distinct.
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
>>> from sage.all import * >>> P = WordPaths('abcdef',steps='triangle_grid');P Word Paths on the triangle grid >>> P('abc').is_simple() True >>> P('abcde').is_simple() True >>> P('abcdef').is_simple() True >>> P('ad').is_simple() True >>> P('aabdee').is_simple() False
- is_tangent()[source]¶
The is_tangent() method, which is implemented for words, has an extended meaning for word paths, which is not implemented yet.
AUTHOR:
Thierry Monteil
- plot_projection(v=None, letters=None, color=None, ring=None, size=12, kind='right')[source]¶
Return an image of the projection of the successive points of the path into the space orthogonal to the given vector.
INPUT:
self
– a word path in a 3 or 4 dimension vector spacev
– vector (default:None
); ifNone
, the directive vector (i.e. the end point minus starting point) of the path is considered.letters
– iterable (default:None
); of the letters to be projected. IfNone
, then all the letters are considered.color
– dictionary (default:None
); of the letters mapped to colors. IfNone
, automatic colors are chosen.ring
– ring (default:None
); where to do the computations. IfNone
, RealField(53) is used.size
– number (default:12
); size of the pointskind
– string (default:'right'
); either'right'
or'left'
. The color of a letter is given to the projected prefix to the right or the left of the letter.
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) # long time (2s) Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> s = WordMorphism('1->12,2->13,3->1') >>> D = s.fixed_point('1') >>> v = s.pisot_eigenvector_right() >>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))]) >>> w = P(D[:Integer(200)]) >>> w.plot_projection(v) # long time (2s) Graphics object consisting of 200 graphics primitives
In this case, the abelianized vector doesn’t give a good projection:
sage: w.plot_projection() # long time (2s) Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> w.plot_projection() # long time (2s) Graphics object consisting of 200 graphics primitives
You can project only the letters you want:
sage: w.plot_projection(v, letters='12') # long time (2s) Graphics object consisting of 168 graphics primitives
>>> from sage.all import * >>> w.plot_projection(v, letters='12') # long time (2s) Graphics object consisting of 168 graphics primitives
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)) # long time (2s) Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> w.plot_projection(v, ring=RealField(Integer(20))) # long time (2s) Graphics object consisting of 200 graphics primitives
You can change the size of the points:
sage: w.plot_projection(v, size=30) # long time (2s) Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> w.plot_projection(v, size=Integer(30)) # long time (2s) Graphics object consisting of 200 graphics primitives
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') # long time (2s) Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> w.plot_projection(v, kind='left') # long time (2s) Graphics object consisting of 200 graphics primitives
To remove the axis, do like this:
sage: r = w.plot_projection(v) # needs sage.plot sage: r.axes(False) # needs sage.plot sage: r # long time (2s) # needs sage.plot Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> r = w.plot_projection(v) # needs sage.plot >>> r.axes(False) # needs sage.plot >>> r # long time (2s) # needs sage.plot Graphics object consisting of 200 graphics primitives
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) # long time (2s) # needs sage.plot Graphics object consisting of 200 graphics primitives
>>> from sage.all import * >>> color = {'1': 'purple', '2': (RealNumber('.2'),RealNumber('.3'),RealNumber('.4')), '3': 'magenta'} >>> w.plot_projection(v, color=color) # long time (2s) # needs sage.plot Graphics object consisting of 200 graphics primitives
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) # needs sage.plot Graphics3d Object
>>> from sage.all import * >>> s = WordMorphism('1->12,2->13,3->14,4->1') >>> D = s.fixed_point('1') >>> v = s.pisot_eigenvector_right() >>> P = WordPaths('1234',[(Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(1))]) >>> w = P(D[:Integer(200)]) >>> w.plot_projection(v) # needs sage.plot Graphics3d Object
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() # needs sage.plot Traceback (most recent call last): ... TypeError: The dimension of the vector space (=2) must be 3 or 4
>>> from sage.all import * >>> P = WordPaths('ab', [(Integer(1), Integer(0)), (Integer(0), Integer(1))]) >>> p = P('aabbabbab') >>> p.plot_projection() # needs sage.plot Traceback (most recent call last): ... TypeError: The dimension of the vector space (=2) must be 3 or 4
- points(include_last=True)[source]¶
Return an iterator yielding a list of points used to draw the path represented by this word.
INPUT:
include_last
– boolean (default:True
); whether to include the last point
EXAMPLES:
A simple closed square:
sage: P = WordPaths('abAB') sage: list(P('abAB').points()) [(0, 0), (1, 0), (1, 1), (0, 1), (0, 0)]
>>> from sage.all import * >>> P = WordPaths('abAB') >>> 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)]
>>> from sage.all import * >>> 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)]
>>> from sage.all import * >>> list(P('abaB').points()) [(0, 0), (1, 0), (1, 1), (2, 1), (2, 0)]
- projected_path(v=None, ring=None)[source]¶
Return the path projected into the space orthogonal to the given vector.
INPUT:
v
– vector (default:None
); ifNone
, the directive vector (i.e. the end point minus starting point) of the path is considered.ring
– ring (default:None
); where to do the computations. IfNone
, RealField(53) is used.
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() # needs sage.plot Graphics object consisting of 3 graphics primitives
>>> from sage.all import * >>> s = WordMorphism('1->12,2->13,3->1') >>> D = s.fixed_point('1') >>> v = s.pisot_eigenvector_right() >>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))]) >>> w = P(D[:Integer(1000)]) >>> p = w.projected_path(v) >>> p Path: 1213121121312121312112131213121121312121... >>> p[:Integer(20)].plot() # needs sage.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)}
>>> from sage.all import * >>> p = w.projected_path(v, RealField(Integer(10))) >>> p Path: 1213121121312121312112131213121121312121... >>> p.parent().letters_to_steps() {'1': (-0.53, 0.00), '2': (0.75, -0.48), '3': (0.41, 0.88)}
- projected_point_iterator(v=None, ring=None)[source]¶
Return an iterator of the projection of the orbit points of the path into the space orthogonal to the given vector.
INPUT:
v
– vector (default:None
); ifNone
, the directive vector (i.e. the end point minus starting point) of the path is consideredring
– ring (default:None
); where to do the computations. IfNone
, RealField(53) is used.
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): next(it) (0.000000000000000, 0.000000000000000) (-0.526233343362516, 0.000000000000000) (0.220830337618112, -0.477656250512816) (-0.305403005744404, -0.477656250512816) (0.100767309386062, 0.400890564600664) (-0.425466033976454, 0.400890564600664)
>>> from sage.all import * >>> s = WordMorphism('1->12,2->13,3->1') >>> D = s.fixed_point('1') >>> v = s.pisot_eigenvector_right() >>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))]) >>> w = P(D[:Integer(200)]) >>> it = w.projected_point_iterator(v) >>> for i in range(Integer(6)): next(it) (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): next(it) (0.00000) (0.78087) (1.5617) (0.93704) (0.31235) (1.0932) (0.46852) (-0.15617)
>>> from sage.all import * >>> P = WordPaths('ab','ne') >>> p = P('aabbabbab') >>> it = p.projected_point_iterator(ring=RealField(Integer(20))) >>> for i in range(Integer(8)): next(it) (0.00000) (0.78087) (1.5617) (0.93704) (0.31235) (1.0932) (0.46852) (-0.15617)
- start_point()[source]¶
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)
>>> from sage.all import * >>> WordPaths('abcdef')('abcdef').start_point() (0, 0) >>> WordPaths('abcdef', steps='cube_grid')('abcdef').start_point() (0, 0, 0) >>> P = WordPaths('ab', steps=[(Integer(1),Integer(0),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0),Integer(0))]) >>> P('abbba').start_point() (0, 0, 0, 0)
- tikz_trajectory()[source]¶
Return the trajectory of
self
as atikz
string.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)'
>>> from sage.all import * >>> P = WordPaths('abcdef') >>> p = P('abcde') >>> 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)'
- class sage.combinat.words.paths.FiniteWordPath_all_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_all_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_all
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid[source]¶
Bases:
FiniteWordPath_3d
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_cube_grid_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_cube_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck[source]¶
Bases:
FiniteWordPath_2d
- class sage.combinat.words.paths.FiniteWordPath_dyck_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_dyck_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_dyck
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid(parent, *args, **kwds)[source]¶
Bases:
FiniteWordPath_triangle_grid
INPUT:
parent
– a parent object inheriting from Words_all that has the alphabet attribute defined*args
,**kwds
– arguments accepted by AbstractWord
EXAMPLES:
sage: F = WordPaths('abcdef', steps='hexagon'); F Word Paths on the hexagonal grid sage: f = F('aaabbbccddef'); f Path: aaabbbccddef
>>> from sage.all import * >>> F = WordPaths('abcdef', steps='hexagon'); F Word Paths on the hexagonal grid >>> f = F('aaabbbccddef'); f Path: aaabbbccddef
sage: f == loads(dumps(f)) True
>>> from sage.all import * >>> f == loads(dumps(f)) True
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_hexagonal_grid_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_hexagonal_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east[source]¶
Bases:
FiniteWordPath_2d
- class sage.combinat.words.paths.FiniteWordPath_north_east_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_north_east_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_north_east
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid[source]¶
Bases:
FiniteWordPath_2d
- area()[source]¶
Return the area of a closed path.
INPUT:
self
– a closed path
EXAMPLES:
sage: P = WordPaths('abAB', steps='square_grid') sage: P('abAB').area() 1 sage: P('aabbAABB').area() 4 sage: P('aabbABAB').area() 3
>>> from sage.all import * >>> P = WordPaths('abAB', steps='square_grid') >>> P('abAB').area() 1 >>> P('aabbAABB').area() 4 >>> 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 k such that 2*k^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, 10181446324101389, 59341817924539925)
>>> from sage.all import * >>> [words.fibonacci_tile(i).area() for i in range(Integer(6))] [1, 5, 29, 169, 985, 5741] >>> [words.dual_fibonacci_tile(i).area() for i in range(Integer(6))] [1, 5, 29, 169, 985, 5741] >>> oeis(_)[Integer(0)] # optional -- internet A001653: Numbers k such that 2*k^2 - 1 is a square. >>> _.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, 10181446324101389, 59341817924539925)
- is_closed()[source]¶
Return whether
self
represents a closed path.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
>>> from sage.all import * >>> P = WordPaths('abAB', steps='square_grid') >>> P('aA').is_closed() True >>> P('abAB').is_closed() True >>> P('ababAABB').is_closed() True >>> P('aaabbbAABB').is_closed() False >>> P('ab').is_closed() False
- is_simple()[source]¶
Return whether the path is simple.
A path is simple if all its points are distinct.
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
>>> from sage.all import * >>> P = WordPaths('abAB', steps='square_grid') >>> P('abab').is_simple() True >>> P('abAB').is_simple() True >>> P('abA').is_simple() True >>> P('aabABB').is_simple() False >>> P().is_simple() True >>> P('A').is_simple() True >>> P('aA').is_simple() True >>> P('aaA').is_simple() False
REFERENCES:
Provençal, X., Combinatoires des mots, géometrie discrète et pavages, Thèse de doctorat en Mathématiques, Montréal, UQAM, septembre 2008, 115 pages.
- tikz_trajectory()[source]¶
Return the trajectory of
self
as atikz
string.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)'
>>> from sage.all import * >>> f = words.fibonacci_tile(Integer(1)) >>> 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)'
- class sage.combinat.words.paths.FiniteWordPath_square_grid_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_square_grid_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_square_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid[source]¶
Bases:
FiniteWordPath_2d
- xmax()[source]¶
Return 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
>>> from sage.all import * >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.xmax() 4.50000000000000 >>> w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC') >>> w.xmax() 4.00000000000000
- xmin()[source]¶
Return 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
>>> from sage.all import * >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.xmin() 0.000000000000000 >>> w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC') >>> w.xmin() -3.00000000000000
- ymax()[source]¶
Return 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
>>> from sage.all import * >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.ymax() 2.59807621135332 >>> w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC') >>> w.ymax() 8.66025403784439
- ymin()[source]¶
Return 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
>>> from sage.all import * >>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC') >>> w.ymin() 0.000000000000000 >>> w = WordPaths('abcABC', steps='triangle')('ABAcacacababababcbcbAC') >>> w.ymin() -0.866025403784439
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_list[source]¶
Bases:
WordDatatype_list
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_str[source]¶
Bases:
WordDatatype_str
,FiniteWordPath_triangle_grid
,FiniteWord_class
- class sage.combinat.words.paths.FiniteWordPath_triangle_grid_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWordPath_triangle_grid
,FiniteWord_class
- sage.combinat.words.paths.WordPaths(alphabet, steps=None)[source]¶
Return the combinatorial class of paths of the given type of steps.
INPUT:
alphabet
– ordered alphabetsteps
– (default:None
) it can be one of the following:an iterable ordered container of as many vectors as there are letters in the alphabet. The vectors are associated to the letters according to their order in steps. The vectors can be a tuple or anything that can be passed to vector function.
an iterable ordered container of k vectors where k is half the size of alphabet. The vectors and their opposites are associated to the letters according to their order in steps (given vectors first, opposite vectors after).
None
– in this case, the type of steps are guessed from the length of alphabet'square_grid'
or'square'
– (default when size of alphabet is 4) The order is : East, North, West, South.'triangle_grid'
or'triangle'
'hexagonal_grid'
or'hexagon'
– (default when size of alphabet is 6)'cube_grid'
or'cube'
'north_east'
,'ne'
or'NE'
– (the default when size of alphabet is 2)'dyck'
OUTPUT: the combinatorial class of all paths of the given type
EXAMPLES:
The steps can be given explicitly:
sage: WordPaths('abc', steps=[(1,2), (-1,4), (0,-3)]) Word Paths over 3 steps
>>> from sage.all import * >>> WordPaths('abc', steps=[(Integer(1),Integer(2)), (-Integer(1),Integer(4)), (Integer(0),-Integer(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
>>> from sage.all import * >>> WordPaths(range(Integer(3)), steps=[(Integer(1),Integer(2)), (-Integer(1),Integer(4)), (Integer(0),-Integer(3))]) Word Paths over 3 steps >>> WordPaths(['cric','crac','croc'], steps=[(Integer(1),Integer(2)), (Integer(1),Integer(4)), (Integer(0),Integer(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
>>> from sage.all import * >>> WordPaths('ab', steps=[(Integer(1),Integer(2),Integer(2)),(-Integer(1),Integer(4),Integer(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))]
>>> from sage.all import * >>> P = WordPaths('abcd', [(Integer(1),Integer(0)), (Integer(0),Integer(1))]) >>> P Word Paths over 4 steps >>> 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
>>> from sage.all import * >>> WordPaths('ab') Word Paths in North and East steps >>> WordPaths(range(Integer(4))) Word Paths on the square grid >>> WordPaths(range(Integer(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
>>> from sage.all import * >>> WordPaths('ab', steps='north_east') Word Paths in North and East steps >>> WordPaths('()', steps='dyck') Finite Dyck paths
On a four letters alphabet:
sage: WordPaths('ruld', steps='square_grid') Word Paths on the square grid
>>> from sage.all import * >>> 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
>>> from sage.all import * >>> WordPaths('abcdef', steps='hexagonal_grid') Word Paths on the hexagonal grid >>> WordPaths('abcdef', steps='triangle_grid') Word Paths on the triangle grid >>> WordPaths('abcdef', steps='cube_grid') Word Paths on the cube grid
- class sage.combinat.words.paths.WordPaths_all(alphabet, steps)[source]¶
Bases:
FiniteWords
The combinatorial class of all paths, i.e of all words over an alphabet where each letter is mapped to a step (a vector).
- letters_to_steps()[source]¶
Return 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))]
>>> from sage.all import * >>> d = WordPaths('ab').letters_to_steps() >>> sorted(d.items()) [('a', (0, 1)), ('b', (1, 0))] >>> d = WordPaths('abcd').letters_to_steps() >>> sorted(d.items()) [('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))] >>> d = WordPaths('abcdef').letters_to_steps() >>> 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))]
- vector_space()[source]¶
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 with sqrt3 = 1.732050807568878? 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 with sqrt3 = 1.732050807568878?
>>> from sage.all import * >>> WordPaths('ab',steps='dyck').vector_space() Ambient free module of rank 2 over the principal ideal domain Integer Ring >>> WordPaths('ab',steps='north_east').vector_space() Ambient free module of rank 2 over the principal ideal domain Integer Ring >>> WordPaths('abcd',steps='square_grid').vector_space() Ambient free module of rank 2 over the principal ideal domain Integer Ring >>> WordPaths('abcdef',steps='hexagonal_grid').vector_space() Vector space of dimension 2 over Number Field in sqrt3 with defining polynomial x^2 - 3 with sqrt3 = 1.732050807568878? >>> WordPaths('abcdef',steps='cube_grid').vector_space() Ambient free module of rank 3 over the principal ideal domain Integer Ring >>> WordPaths('abcdef',steps='triangle_grid').vector_space() Vector space of dimension 2 over Number Field in sqrt3 with defining polynomial x^2 - 3 with sqrt3 = 1.732050807568878?
- class sage.combinat.words.paths.WordPaths_cube_grid(alphabet)[source]¶
Bases:
WordPaths_all
The combinatorial class of all paths on the cube grid.
- class sage.combinat.words.paths.WordPaths_dyck(alphabet)[source]¶
Bases:
WordPaths_all
The combinatorial class of all Dyck paths.
- class sage.combinat.words.paths.WordPaths_hexagonal_grid(alphabet)[source]¶
Bases:
WordPaths_triangle_grid
The combinatorial class of all paths on the hexagonal grid.
- class sage.combinat.words.paths.WordPaths_north_east(alphabet)[source]¶
Bases:
WordPaths_all
The combinatorial class of all paths using North and East directions.
- class sage.combinat.words.paths.WordPaths_square_grid(alphabet)[source]¶
Bases:
WordPaths_all
The combinatorial class of all paths on the square grid.
- class sage.combinat.words.paths.WordPaths_triangle_grid(alphabet)[source]¶
Bases:
WordPaths_all
The combinatorial class of all paths on the triangle grid.