Maps between finite sets#

This module implements parents modeling the set of all maps between two finite sets. At the user level, any such parent should be constructed using the factory class FiniteSetMaps which properly selects which of its subclasses to use.

AUTHORS:

  • Florent Hivert

class sage.sets.finite_set_maps.FiniteSetEndoMaps_N(n, action, category=None)[source]#

Bases: FiniteSetMaps_MN

The sets of all maps from \(\{1, 2, \dots, n\}\) to itself

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • n – an integer.

  • category – the category in which the sets of maps is constructed. It must be a sub-category of Monoids().Finite() and EnumeratedSets().Finite() which is the default value.

Element[source]#

alias of FiniteSetEndoMap_N

an_element()[source]#

Returns a map in self

EXAMPLES:

sage: M = FiniteSetMaps(4)
sage: M.an_element()
[3, 2, 1, 0]

>>> from sage.all import *
>>> M = FiniteSetMaps(Integer(4))
>>> M.an_element()
[3, 2, 1, 0]
one()[source]#

EXAMPLES:

sage: M = FiniteSetMaps(4)
sage: M.one()
[0, 1, 2, 3]

>>> from sage.all import *
>>> M = FiniteSetMaps(Integer(4))
>>> M.one()
[0, 1, 2, 3]
class sage.sets.finite_set_maps.FiniteSetEndoMaps_Set(domain, action, category=None)[source]#

Bases: FiniteSetMaps_Set, FiniteSetEndoMaps_N

The sets of all maps from a set to itself

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • domain – an object in the category FiniteSets().

  • category – the category in which the sets of maps is constructed. It must be a sub-category of Monoids().Finite() and EnumeratedSets().Finite() which is the default value.

Element[source]#

alias of FiniteSetEndoMap_Set

class sage.sets.finite_set_maps.FiniteSetMaps[source]#

Bases: UniqueRepresentation, Parent

Maps between finite sets

Constructs the set of all maps between two sets. The sets can be given using any of the three following ways:

  1. an object in the category Sets().

  2. a finite iterable. In this case, an object of the class FiniteEnumeratedSet is constructed from the iterable.

  3. an integer n designing the set \(\{0, 1, \dots, n-1\}\). In this case an object of the class IntegerRange is constructed.

INPUT:

  • domain – a set, finite iterable, or integer.

  • codomain – a set, finite iterable, integer, or None (default). In this last case, the maps are endo-maps of the domain.

  • action – "left" (default) or "right". The side where the maps act on the domain. This is used in particular to define the meaning of the product (composition) of two maps.

  • category – the category in which the sets of maps is constructed. By default, this is FiniteMonoids() if the domain and codomain coincide, and FiniteEnumeratedSets() otherwise.

OUTPUT:

an instance of a subclass of FiniteSetMaps modeling the set of all maps between domain and codomain.

EXAMPLES:

We construct the set M of all maps from \(\{a,b\}\) to \(\{3,4,5\}\):

sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5]); M
Maps from {'a', 'b'} to {3, 4, 5}
sage: M.cardinality()
9
sage: M.domain()
{'a', 'b'}
sage: M.codomain()
{3, 4, 5}
sage: for f in M: print(f)
map: a -> 3, b -> 3
map: a -> 3, b -> 4
map: a -> 3, b -> 5
map: a -> 4, b -> 3
map: a -> 4, b -> 4
map: a -> 4, b -> 5
map: a -> 5, b -> 3
map: a -> 5, b -> 4
map: a -> 5, b -> 5

>>> from sage.all import *
>>> M = FiniteSetMaps(["a", "b"], [Integer(3), Integer(4), Integer(5)]); M
Maps from {'a', 'b'} to {3, 4, 5}
>>> M.cardinality()
9
>>> M.domain()
{'a', 'b'}
>>> M.codomain()
{3, 4, 5}
>>> for f in M: print(f)
map: a -> 3, b -> 3
map: a -> 3, b -> 4
map: a -> 3, b -> 5
map: a -> 4, b -> 3
map: a -> 4, b -> 4
map: a -> 4, b -> 5
map: a -> 5, b -> 3
map: a -> 5, b -> 4
map: a -> 5, b -> 5

Elements can be constructed from functions and dictionaries:

sage: M(lambda c: ord(c)-94)
map: a -> 3, b -> 4

sage: M.from_dict({'a':3, 'b':5})
map: a -> 3, b -> 5

>>> from sage.all import *
>>> M(lambda c: ord(c)-Integer(94))
map: a -> 3, b -> 4

>>> M.from_dict({'a':Integer(3), 'b':Integer(5)})
map: a -> 3, b -> 5

If the domain is equal to the codomain, then maps can be composed:

sage: M = FiniteSetMaps([1, 2, 3])
sage: f = M.from_dict({1:2, 2:1, 3:3}); f
map: 1 -> 2, 2 -> 1, 3 -> 3
sage: g = M.from_dict({1:2, 2:3, 3:1}); g
map: 1 -> 2, 2 -> 3, 3 -> 1

sage: f * g
map: 1 -> 1, 2 -> 3, 3 -> 2

>>> from sage.all import *
>>> M = FiniteSetMaps([Integer(1), Integer(2), Integer(3)])
>>> f = M.from_dict({Integer(1):Integer(2), Integer(2):Integer(1), Integer(3):Integer(3)}); f
map: 1 -> 2, 2 -> 1, 3 -> 3
>>> g = M.from_dict({Integer(1):Integer(2), Integer(2):Integer(3), Integer(3):Integer(1)}); g
map: 1 -> 2, 2 -> 3, 3 -> 1

>>> f * g
map: 1 -> 1, 2 -> 3, 3 -> 2

This makes \(M\) into a monoid:

sage: M.category()
Category of finite enumerated monoids
sage: M.one()
map: 1 -> 1, 2 -> 2, 3 -> 3

>>> from sage.all import *
>>> M.category()
Category of finite enumerated monoids
>>> M.one()
map: 1 -> 1, 2 -> 2, 3 -> 3

By default, composition is from right to left, which corresponds to an action on the left. If one specifies action to right, then the composition is from left to right:

sage: M = FiniteSetMaps([1, 2, 3], action = 'right')
sage: f = M.from_dict({1:2, 2:1, 3:3})
sage: g = M.from_dict({1:2, 2:3, 3:1})
sage: f * g
map: 1 -> 3, 2 -> 2, 3 -> 1

>>> from sage.all import *
>>> M = FiniteSetMaps([Integer(1), Integer(2), Integer(3)], action = 'right')
>>> f = M.from_dict({Integer(1):Integer(2), Integer(2):Integer(1), Integer(3):Integer(3)})
>>> g = M.from_dict({Integer(1):Integer(2), Integer(2):Integer(3), Integer(3):Integer(1)})
>>> f * g
map: 1 -> 3, 2 -> 2, 3 -> 1

If the domains and codomains are both of the form \(\{0,\dots\}\), then one can use the shortcut:

sage: M = FiniteSetMaps(2,3); M
Maps from {0, 1} to {0, 1, 2}
sage: M.cardinality()
9

>>> from sage.all import *
>>> M = FiniteSetMaps(Integer(2),Integer(3)); M
Maps from {0, 1} to {0, 1, 2}
>>> M.cardinality()
9

For a compact notation, the elements are then printed as lists \([f(i), i=0,\dots]\):

sage: list(M)
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

>>> from sage.all import *
>>> list(M)
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
cardinality()[source]#

The cardinality of self

EXAMPLES:

sage: FiniteSetMaps(4, 3).cardinality()
81

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3)).cardinality()
81
class sage.sets.finite_set_maps.FiniteSetMaps_MN(m, n, category=None)[source]#

Bases: FiniteSetMaps

The set of all maps from \(\{1, 2, \dots, m\}\) to \(\{1, 2, \dots, n\}\).

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • m, n – integers

  • category – the category in which the sets of maps is constructed. It must be a sub-category of EnumeratedSets().Finite() which is the default value.

Element[source]#

alias of FiniteSetMap_MN

an_element()[source]#

Returns a map in self

EXAMPLES:

sage: M = FiniteSetMaps(4, 2)
sage: M.an_element()
[0, 0, 0, 0]

sage: M = FiniteSetMaps(0, 0)
sage: M.an_element()
[]

>>> from sage.all import *
>>> M = FiniteSetMaps(Integer(4), Integer(2))
>>> M.an_element()
[0, 0, 0, 0]

>>> M = FiniteSetMaps(Integer(0), Integer(0))
>>> M.an_element()
[]

An exception EmptySetError is raised if this set is empty, that is if the codomain is empty and the domain is not.

sage: M = FiniteSetMaps(4, 0)
sage: M.cardinality()
0
sage: M.an_element()
Traceback (most recent call last):
...
EmptySetError

>>> from sage.all import *
>>> M = FiniteSetMaps(Integer(4), Integer(0))
>>> M.cardinality()
0
>>> M.an_element()
Traceback (most recent call last):
...
EmptySetError
codomain()[source]#

The codomain of self

EXAMPLES:

sage: FiniteSetMaps(3,2).codomain()
{0, 1}

>>> from sage.all import *
>>> FiniteSetMaps(Integer(3),Integer(2)).codomain()
{0, 1}
domain()[source]#

The domain of self

EXAMPLES:

sage: FiniteSetMaps(3,2).domain()
{0, 1, 2}

>>> from sage.all import *
>>> FiniteSetMaps(Integer(3),Integer(2)).domain()
{0, 1, 2}
class sage.sets.finite_set_maps.FiniteSetMaps_Set(domain, codomain, category=None)[source]#

Bases: FiniteSetMaps_MN

The sets of all maps between two sets

Users should use the factory class FiniteSetMaps to create instances of this class.

INPUT:

  • domain – an object in the category FiniteSets().

  • codomain – an object in the category FiniteSets().

  • category – the category in which the sets of maps is constructed. It must be a sub-category of EnumeratedSets().Finite() which is the default value.

Element[source]#

alias of FiniteSetMap_Set

codomain()[source]#

The codomain of self

EXAMPLES:

sage: FiniteSetMaps(["a", "b"], [3, 4, 5]).codomain()
{3, 4, 5}

>>> from sage.all import *
>>> FiniteSetMaps(["a", "b"], [Integer(3), Integer(4), Integer(5)]).codomain()
{3, 4, 5}
domain()[source]#

The domain of self

EXAMPLES:

sage: FiniteSetMaps(["a", "b"], [3, 4, 5]).domain()
{'a', 'b'}

>>> from sage.all import *
>>> FiniteSetMaps(["a", "b"], [Integer(3), Integer(4), Integer(5)]).domain()
{'a', 'b'}
from_dict(d)[source]#

Create a map from a dictionary

EXAMPLES:

sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: M.from_dict({"a": 4, "b": 3})
map: a -> 4, b -> 3

>>> from sage.all import *
>>> M = FiniteSetMaps(["a", "b"], [Integer(3), Integer(4), Integer(5)])
>>> M.from_dict({"a": Integer(4), "b": Integer(3)})
map: a -> 4, b -> 3