Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Indexed Monoids
AUTHORS:
- Travis Scrimshaw (2013-10-15) """
#***************************************************************************** # Copyright (C) 2013 Travis Scrimshaw <tscrim at ucdavis.edu> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #*****************************************************************************
""" An element of an indexed monoid.
This is an abstract class which uses the (abstract) method :meth:`_sorted_items` for all of its functions. So to implement an element of an indexed monoid, one just needs to implement :meth:`_sorted_items`, which returns a list of pairs ``(i, p)`` where ``i`` is the index and ``p`` is the corresponding power, sorted in some order. For example, in the free monoid there is no such choice, but for the free abelian monoid, one could want lex order or have the highest powers first.
Indexed monoid elements are ordered lexicographically with respect to the result of :meth:`_sorted_items` (which for abelian free monoids is influenced by the order on the indexing set). """ """ Create the element ``x`` of an indexed free abelian monoid ``F``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.gen(1) F[1] sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: x = a^2 * b^3 * a^2 * b^4; x F[0]^4*F[1]^7 sage: TestSuite(x).run()
sage: F = FreeMonoid(index_set=tuple('abcde')) sage: a,b,c,d,e = F.gens() sage: a in F True sage: a*b in F True sage: TestSuite(a*d^2*e*c*a).run() """
def _sorted_items(self): """ Return the sorted items (i.e factors) of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: x = a*b^2*e*d sage: x._sorted_items() ((0, 1), (1, 2), (4, 1), (3, 1))
.. SEEALSO::
:meth:`_repr_`, :meth:`_latex_`, :meth:`print_options` """
""" Return a string representation of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: a*b^2*e*d F[0]*F[1]^2*F[3]*F[4] """
r""" Return an ASCII art representation of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: ascii_art(a*e*d) F *F *F 0 3 4 sage: ascii_art(a*b^2*e*d) 2 F *F *F *F 0 1 3 4 """
return AsciiArt(["1"])
else: else:
r""" Return a `\LaTeX` representation of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: latex(a*b^2*e*d) F_{0} F_{1}^{2} F_{3} F_{4} """ return '1'
""" Iterate over ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: list(b*a*c^3*b) [(F[1], 1), (F[0], 1), (F[2], 3), (F[1], 1)]
::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: list(b*c^3*a) [(F[0], 1), (F[1], 1), (F[2], 3)] """
r""" Comparisons
TESTS::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: a == a True sage: a*e == a*e True sage: a*b*c^3*b*d == (a*b*c)*(c^2*b*d) True sage: a != b True sage: a*b != b*a True sage: a*b*c^3*b*d != (a*b*c)*(c^2*b*d) False
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: a < b True sage: a*b < b*a True sage: a*b < a*a False sage: a^2*b < a*b*b True sage: b > a True sage: a*b > b*a False sage: a*b > a*a True sage: a*b <= b*a True sage: a*b <= b*a True
sage: FA = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [FA.gen(i) for i in range(5)] sage: a == a True sage: a*e == e*a True sage: a*b*c^3*b*d == a*d*(b^2*c^2)*c True sage: a != b True sage: a*b != a*a True sage: a*b*c^3*b*d != a*d*(b^2*c^2)*c False """ # Equal # Not equal
""" Return a list of the objects indexing ``self`` with non-zero exponents.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*a*c^3*b).support() [0, 1, 2]
::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (a*c^3).support() [0, 2] """
""" Return the support of the leading generator of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*a*c^3*a).leading_support() 1
::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*c^3*a).leading_support() 0 """ return None
""" Return the support of the trailing generator of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*a*c^3*a).trailing_support() 0
::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*c^3*a).trailing_support() 2 """ return None
""" Return ``self`` as a word represented as a list whose entries are indices of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*a*c^3*a).to_word_list() [1, 0, 2, 2, 2, 0]
::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (b*c^3*a).to_word_list() [0, 1, 2, 2, 2] """
""" An element of an indexed free abelian monoid. """ """ Create the element ``x`` of an indexed free abelian monoid ``F``.
EXAMPLES::
sage: F = FreeMonoid(index_set=tuple('abcde')) sage: x = F( [(1, 2), (0, 1), (3, 2), (0, 1)] ) sage: y = F( ((1, 2), (0, 1), [3, 2], [0, 1]) ) sage: z = F( reversed([(0, 1), (3, 2), (0, 1), (1, 2)]) ) sage: x == y and y == z True sage: TestSuite(x).run() """
r""" TESTS::
sage: F = FreeMonoid(index_set=tuple('abcde')) sage: hash(F ([(1,2),(0,1)]) ) 2401565693828035651 # 64-bit 1164080195 # 32-bit sage: hash(F ([(0,2),(1,1)]) ) -3359280905493236379 # 64-bit -1890405019 # 32-bit """
""" Return the sorted items (i.e factors) of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: x = a*b^2*e*d sage: x._sorted_items() ((0, 1), (1, 2), (4, 1), (3, 1)) sage: F.print_options(sorting_reverse=True) sage: x._sorted_items() ((0, 1), (1, 2), (4, 1), (3, 1)) sage: F.print_options(sorting_reverse=False) # reset to original state
.. SEEALSO::
:meth:`_repr_`, :meth:`_latex_`, :meth:`print_options` """
""" Multiply ``self`` by ``other``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: a*b^2*e*d F[0]*F[1]^2*F[4]*F[3] sage: (a*b^2*d^2) * (d^4*b*e) F[0]*F[1]^2*F[3]^6*F[1]*F[4] """
""" Return the length of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: elt = a*c^3*b^2*a sage: elt.length() 7 sage: len(elt) 7 """
""" An element of an indexed free abelian monoid. """ """ Create the element ``x`` of an indexed free abelian monoid ``F``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: x = F([(0, 1), (2, 2), (-1, 2)]) sage: y = F({0:1, 2:2, -1:2}) sage: z = F(reversed([(0, 1), (2, 2), (-1, 2)])) sage: x == y and y == z True sage: TestSuite(x).run() """
""" Return the sorted items (i.e factors) of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: x = a*b^2*e*d sage: x._sorted_items() [(0, 1), (1, 2), (3, 1), (4, 1)] sage: F.print_options(sorting_reverse=True) sage: x._sorted_items() [(4, 1), (3, 1), (1, 2), (0, 1)] sage: F.print_options(sorting_reverse=False) # reset to original state
.. SEEALSO::
:meth:`_repr_`, :meth:`_latex_`, :meth:`print_options` """ reverse=print_options['sorting_reverse']) except Exception: # Sorting the output is a plus, but if we can't, no big deal pass
r""" TESTS::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: hash( F([(0,1), (2,2)]) ) 8087055352805725849 # 64-bit 250091161 # 32-bit sage: hash( F([(2,1)]) ) 5118585357534560720 # 64-bit 1683816912 # 32-bit """
""" Multiply ``self`` by ``other``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: a*b^2*e*d F[0]*F[1]^2*F[3]*F[4] """ blas.add(self._monomial, other._monomial))
""" Raise ``self`` to the power of ``n``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: x = a*b^2*e*d; x F[0]*F[1]^2*F[3]*F[4] sage: x^3 F[0]^3*F[1]^6*F[3]^3*F[4]^3 sage: x^0 1 """ raise TypeError("Argument n (= {}) must be an integer".format(n)) raise ValueError("Argument n (= {}) must be positive".format(n))
""" Cancel the element ``elt`` out of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: elt = a*b*c^3*d^2; elt F[0]*F[1]*F[2]^3*F[3]^2 sage: elt // a F[1]*F[2]^3*F[3]^2 sage: elt // c F[0]*F[1]*F[2]^2*F[3]^2 sage: elt // (a*b*d^2) F[2]^3 sage: elt // a^4 Traceback (most recent call last): ... ValueError: invalid cancellation sage: elt // e^4 Traceback (most recent call last): ... ValueError: invalid cancellation """
""" Return the length of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: elt = a*c^3*b^2*a sage: elt.length() 7 sage: len(elt) 7 """
""" Return ``self`` as a dictionary.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: a,b,c,d,e = [F.gen(i) for i in range(5)] sage: (a*c^3).dict() {0: 1, 2: 3} """
""" Base class for monoids with an indexed set of generators.
INPUT:
- ``indices`` -- the indices for the generators
For the optional arguments that control the printing, see :class:`~sage.structure.indexed_generators.IndexedGenerators`. """ """ TESTS::
sage: F = FreeAbelianMonoid(index_set=['a','b','c']) sage: G = FreeAbelianMonoid(index_set=('a','b','c')) sage: H = FreeAbelianMonoid(index_set=tuple('abc')) sage: F is G and F is H True
sage: F = FreeAbelianMonoid(index_set=['a','b','c'], latex_bracket=['LEFT', 'RIGHT']) sage: F.print_options()['latex_bracket'] ('LEFT', 'RIGHT') sage: F is G False sage: Groups.Commutative.free() Traceback (most recent call last): ... ValueError: either the indices or names must be given """
# bracket or latex_bracket might be lists, so convert # them to tuples so that they're hashable.
names=names, **kwds)
""" Initialize ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: TestSuite(F).run() sage: F = FreeMonoid(index_set=tuple('abcde')) sage: TestSuite(F).run()
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: TestSuite(F).run() sage: F = FreeAbelianMonoid(index_set=tuple('abcde')) sage: TestSuite(F).run() """ else:
# ignore the optional 'key' since it only affects CachedRepresentation
""" Used by the preparser for ``F.<x> = ...``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: F._first_ngens(3) (F[0], F[1], F[-1]) """
""" Create an element of this abelian monoid from ``x``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F(F.gen(2)) F[2] sage: F([[1, 3], [-2, 12]]) F[-2]^12*F[1]^3 sage: F(-5) Traceback (most recent call last): ... TypeError: unable to convert -5, use gen() instead """ return self.one()
""" Return an element of ``self``.
EXAMPLES::
sage: G = FreeAbelianMonoid(index_set=ZZ) sage: G.an_element() F[-1]^3*F[0]*F[1]^3 sage: G = FreeMonoid(index_set=tuple('ab')) sage: G.an_element() F['a']^2*F['b']^2 """ except Exception: pass
r""" Return the cardinality of ``self``, which is `\infty` unless this is the trivial monoid.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: F.cardinality() +Infinity sage: F = FreeMonoid(index_set=()) sage: F.cardinality() 1
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.cardinality() +Infinity sage: F = FreeAbelianMonoid(index_set=()) sage: F.cardinality() 1 """
def monoid_generators(self): """ Return the monoid generators of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.monoid_generators() Lazy family (Generator map from Integer Ring to Free abelian monoid indexed by Integer Ring(i))_{i in Integer Ring} sage: F = FreeAbelianMonoid(index_set=tuple('abcde')) sage: sorted(F.monoid_generators()) [F['a'], F['b'], F['c'], F['d'], F['e']] """
""" Free monoid with an indexed set of generators.
INPUT:
- ``indices`` -- the indices for the generators
For the optional arguments that control the printing, see :class:`~sage.structure.indexed_generators.IndexedGenerators`.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: F.gen(15)^3 * F.gen(2) * F.gen(15) F[15]^3*F[2]*F[15] sage: F.gen(1) F[1]
Now we examine some of the printing options::
sage: F = FreeMonoid(index_set=ZZ, prefix='X', bracket=['|','>']) sage: F.gen(2) * F.gen(12) X|2>*X|12> """ """ Return a string representation of ``self``.
EXAMPLES::
sage: FreeMonoid(index_set=ZZ) Free monoid indexed by Integer Ring """
def one(self): """ Return the identity element of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: F.one() 1 """
""" The generator indexed by ``x`` of ``self``.
EXAMPLES::
sage: F = FreeMonoid(index_set=ZZ) sage: F.gen(0) F[0] sage: F.gen(2) F[2]
TESTS::
sage: F = FreeMonoid(index_set=[1,2]) sage: F.gen(2) F[2] sage: F.gen(0) Traceback (most recent call last): ... IndexError: 0 is not in the index set """
""" Free abelian monoid with an indexed set of generators.
INPUT:
- ``indices`` -- the indices for the generators
For the optional arguments that control the printing, see :class:`~sage.structure.indexed_generators.IndexedGenerators`.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.gen(15)^3 * F.gen(2) * F.gen(15) F[2]*F[15]^4 sage: F.gen(1) F[1]
Now we examine some of the printing options::
sage: F = FreeAbelianMonoid(index_set=Partitions(), prefix='A', bracket=False, scalar_mult='%') sage: F.gen([3,1,1]) * F.gen([2,2]) A[2, 2]%A[3, 1, 1] """ """ Return a string representation of ``self``.
EXAMPLES::
sage: FreeAbelianMonoid(index_set=ZZ) Free abelian monoid indexed by Integer Ring """
""" Create an element of ``self`` from ``x``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F(F.gen(2)) F[2] sage: F([[1, 3], [-2, 12]]) F[-2]^12*F[1]^3 sage: F({1:3, -2: 12}) F[-2]^12*F[1]^3
TESTS::
sage: F([(1, 3), (1, 2)]) F[1]^5
sage: F([(42, 0)]) 1 sage: F({42: 0}) 1 """ else:
def one(self): """ Return the identity element of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.one() 1 """
""" The generator indexed by ``x`` of ``self``.
EXAMPLES::
sage: F = FreeAbelianMonoid(index_set=ZZ) sage: F.gen(0) F[0] sage: F.gen(2) F[2]
TESTS::
sage: F = FreeAbelianMonoid(index_set=[1,2]) sage: F.gen(2) F[2] sage: F.gen(0) Traceback (most recent call last): ... IndexError: 0 is not in the index set """ except (TypeError, NotImplementedError): # Backup (e.g., if it is a string) return self.element_class(self, {x:1})
|