Data structures for maps between finite sets#
This module implements several fast Cython data structures for maps
between two finite set. Those classes are not intended to be used
directly. Instead, such a map should be constructed via its parent,
using the class FiniteSetMaps
.
EXAMPLES:
To create a map between two sets, one first creates the set of such maps:
sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5])
The map can then be constructed either from a function:
sage: f1 = M(lambda c: ord(c)-94); f1
map: a -> 3, b -> 4
or from a dictionary:
sage: f2 = M.from_dict({'a':3, 'b':4}); f2
map: a -> 3, b -> 4
The two created maps are equal:
sage: f1 == f2
True
Internally, maps are represented as the list of the ranks of the
images f(x)
in the co-domain, in the order of the domain:
sage: list(f2)
[0, 1]
A third fast way to create a map it to use such a list. it should be kept for internal use:
sage: f3 = M._from_list_([0, 1]); f3
map: a -> 3, b -> 4
sage: f1 == f3
True
AUTHORS:
Florent Hivert
- class sage.sets.finite_set_map_cy.FiniteSetEndoMap_N#
Bases:
FiniteSetMap_MN
Maps from
range(n)
to itself.See also
FiniteSetMap_MN
for assumptions on the parent
- class sage.sets.finite_set_map_cy.FiniteSetEndoMap_Set#
Bases:
FiniteSetMap_Set
Maps from a set to itself
See also
FiniteSetMap_Set
for assumptions on the parent
- class sage.sets.finite_set_map_cy.FiniteSetMap_MN#
Bases:
ClonableIntArray
Data structure for maps from
range(m)
torange(n)
.We assume that the parent given as argument is such that:
m
is stored inself.parent()._m
n
is stored inself.parent()._n
the domain is in
self.parent().domain()
the codomain is in
self.parent().codomain()
- check()#
Performs checks on
self
Check that
self
is a proper function and then callsparent.check_element(self)
whereparent
is the parent ofself
.
- codomain()#
Returns the codomain of
self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).codomain() {0, 1, 2}
- domain()#
Returns the domain of
self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).domain() {0, 1, 2, 3}
- fibers()#
Returns the fibers of
self
OUTPUT:
a dictionary
d
such thatd[y]
is the set of allx
indomain
such thatf(x) = y
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).fibers() {0: {1}, 1: {0, 3}, 2: {2}} sage: F = FiniteSetMaps(["a", "b", "c"]) sage: F.from_dict({"a": "b", "b": "a", "c": "b"}).fibers() == {'a': {'b'}, 'b': {'a', 'c'}} True
- getimage(i)#
Returns the image of
i
byself
INPUT:
i
– any object.
Note
if you need speed, please use instead
_getimage()
EXAMPLES:
sage: fs = FiniteSetMaps(4, 3)([1, 0, 2, 1]) sage: fs.getimage(0), fs.getimage(1), fs.getimage(2), fs.getimage(3) (1, 0, 2, 1)
- image_set()#
Returns the image set of
self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).image_set() {0, 1, 2} sage: FiniteSetMaps(4, 3)([1, 0, 0, 1]).image_set() {0, 1}
- items()#
The items of
self
Return the list of the ordered pairs
(x, self(x))
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).items() [(0, 1), (1, 0), (2, 2), (3, 1)]
- setimage(i, j)#
Set the image of
i
asj
inself
Warning
self
must be mutable; otherwise an exception is raised.INPUT:
i
,j
– twoobject
’s
OUTPUT:
None
Note
if you need speed, please use instead
_setimage()
EXAMPLES:
sage: fs = FiniteSetMaps(4, 3)([1, 0, 2, 1]) sage: fs2 = copy(fs) sage: fs2.setimage(2, 1) sage: fs2 [1, 0, 1, 1] sage: with fs.clone() as fs3: ....: fs3.setimage(0, 2) ....: fs3.setimage(1, 2) sage: fs3 [2, 2, 2, 1]
- class sage.sets.finite_set_map_cy.FiniteSetMap_Set#
Bases:
FiniteSetMap_MN
Data structure for maps
We assume that the parent given as argument is such that:
the domain is in
parent.domain()
the codomain is in
parent.codomain()
parent._m
contains the cardinality of the domainparent._n
contains the cardinality of the codomainparent._unrank_domain
andparent._rank_domain
is a pair of reciprocal rank and unrank functions between the domain andrange(parent._m)
.parent._unrank_codomain
andparent._rank_codomain
is a pair of reciprocal rank and unrank functions between the codomain andrange(parent._n)
.
- classmethod from_dict(t, parent, d)#
Creates a
FiniteSetMap
from a dictionaryWarning
no check is performed !
- classmethod from_list(t, parent, lst)#
Creates a
FiniteSetMap
from a listWarning
no check is performed !
- getimage(i)#
Returns the image of
i
byself
INPUT:
i
– anint
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c", "d"], ["u", "v", "w"]) sage: fs = F._from_list_([1, 0, 2, 1]) sage: list(map(fs.getimage, ["a", "b", "c", "d"])) ['v', 'u', 'w', 'v']
- image_set()#
Returns the image set of
self
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c"]) sage: sorted(F.from_dict({"a": "b", "b": "a", "c": "b"}).image_set()) ['a', 'b'] sage: F = FiniteSetMaps(["a", "b", "c"]) sage: F(lambda x: "c").image_set() {'c'}
- items()#
The items of
self
Return the list of the couple
(x, self(x))
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c"]) sage: F.from_dict({"a": "b", "b": "a", "c": "b"}).items() [('a', 'b'), ('b', 'a'), ('c', 'b')]
- setimage(i, j)#
Set the image of
i
asj
inself
Warning
self
must be mutable otherwise an exception is raised.INPUT:
i
,j
– twoobject
’s
OUTPUT:
None
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c", "d"], ["u", "v", "w"]) sage: fs = F(lambda x: "v") sage: fs2 = copy(fs) sage: fs2.setimage("a", "w") sage: fs2 map: a -> w, b -> v, c -> v, d -> v sage: with fs.clone() as fs3: ....: fs3.setimage("a", "u") ....: fs3.setimage("c", "w") sage: fs3 map: a -> u, b -> v, c -> w, d -> v
- sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_dict(t, parent, d)#
Creates a
FiniteSetMap
from a dictionaryWarning
no check is performed !
- sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_list(t, parent, lst)#
Creates a
FiniteSetMap
from a listWarning
no check is performed !
- sage.sets.finite_set_map_cy.fibers(f, domain)#
Returns the fibers of the function
f
on the finite setdomain
INPUT:
f
– a function or callabledomain
– a finite iterable
OUTPUT:
a dictionary
d
such thatd[y]
is the set of allx
indomain
such thatf(x) = y
EXAMPLES:
sage: from sage.sets.finite_set_map_cy import fibers, fibers_args sage: fibers(lambda x: 1, []) {} sage: fibers(lambda x: x^2, [-1, 2, -3, 1, 3, 4]) {1: {1, -1}, 4: {2}, 9: {3, -3}, 16: {4}} sage: fibers(lambda x: 1, [-1, 2, -3, 1, 3, 4]) {1: {1, 2, 3, 4, -3, -1}} sage: fibers(lambda x: 1, [1,1,1]) {1: {1}}
See also
fibers_args()
if one needs to pass extra arguments tof
.
- sage.sets.finite_set_map_cy.fibers_args(f, domain, *args, **opts)#
Returns the fibers of the function
f
on the finite setdomain
It is the same as
fibers()
except that one can pass extra argument forf
(with a small overhead)EXAMPLES:
sage: from sage.sets.finite_set_map_cy import fibers_args sage: fibers_args(operator.pow, [-1, 2, -3, 1, 3, 4], 2) {1: {1, -1}, 4: {2}, 9: {3, -3}, 16: {4}}