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:
sage.sets.finite_set_map_cy.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:
sage.sets.finite_set_map_cy.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:
sage.structure.list_clone.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:
sage.sets.finite_set_map_cy.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}}