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:
Bases: sage.sets.finite_set_map_cy.FiniteSetMap_MN
Maps from range(n) to itself.
See also
FiniteSetMap_MN for assumptions on the parent
TESTS:
sage: fs = FiniteSetMaps(3)([1, 0, 2])
sage: TestSuite(fs).run()
Bases: sage.sets.finite_set_map_cy.FiniteSetMap_Set
Maps from a set to itself
See also
FiniteSetMap_Set for assumptions on the parent
TESTS:
sage: F = FiniteSetMaps(["a", "b", "c"])
sage: f = F.from_dict({"a": "b", "b": "a", "c": "b"}); f
map: a -> b, b -> a, c -> b
sage: TestSuite(f).run()
Bases: sage.structure.list_clone.ClonableIntArray
Data structure for maps from range(m) to range(n).
We assume that the parent given as argument is such that:
Performs checks on self
Check that self is a proper function and then calls parent.check_element(self) where parent is the parent of self.
TESTS:
sage: fs = FiniteSetMaps(3, 2)
sage: for el in fs: el.check()
sage: fs([1,1])
Traceback (most recent call last):
...
AssertionError: Wrong number of values
sage: fs([0,0,2])
Traceback (most recent call last):
...
AssertionError: Wrong value self(2) = 2
Returns the codomain of self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).codomain()
{0, 1, 2}
Returns the domain of self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).domain()
{0, 1, 2, 3}
Returns the fibers of self
OUTPUT:
a dictionary d such that d[y] is the set of all x in domain such that f(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'}}
Returns the image of i by self
INPUT:
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)
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}
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)]
Set the image of i as j in self
Warning
self must be mutable; otherwise an exception is raised.
INPUT:
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]
Bases: sage.sets.finite_set_map_cy.FiniteSetMap_MN
Data structure for maps
We assume that the parent given as argument is such that:
Creates a FiniteSetMap from a dictionary
Warning
no check is performed !
TESTS:
sage: from sage.sets.finite_set_map_cy import FiniteSetMap_Set_from_dict as from_dict
sage: F = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: f = from_dict(F.element_class, F, {"a": 3, "b": 5}); f.check(); f
map: a -> 3, b -> 5
sage: f.parent() is F
True
sage: f.is_immutable()
True
Creates a FiniteSetMap from a list
Warning
no check is performed !
TESTS:
sage: from sage.sets.finite_set_map_cy import FiniteSetMap_Set_from_list as from_list
sage: F = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: f = from_list(F.element_class, F, [0,2]); f.check(); f
map: a -> 3, b -> 5
sage: f.parent() is F
True
sage: f.is_immutable()
True
Returns the image of i by self
INPUT:
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c", "d"], ["u", "v", "w"])
sage: fs = F._from_list_([1, 0, 2, 1])
sage: map(fs.getimage, ["a", "b", "c", "d"])
['v', 'u', 'w', 'v']
Returns the image set of self
EXAMPLES:
sage: F = FiniteSetMaps(["a", "b", "c"])
sage: 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'}
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')]
TESTS:
sage: all(F.from_dict(dict(f.items())) == f for f in F)
True
Set the image of i as j in self
Warning
self must be mutable otherwise an exception is raised.
INPUT:
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
TESTS:
sage: with fs.clone() as fs3:
... fs3.setimage("z", 2)
Traceback (most recent call last):
...
ValueError: 'z' is not in list
sage: with fs.clone() as fs3:
... fs3.setimage(1, 4)
Traceback (most recent call last):
...
ValueError: 1 is not in list
Creates a FiniteSetMap from a dictionary
Warning
no check is performed !
TESTS:
sage: from sage.sets.finite_set_map_cy import FiniteSetMap_Set_from_dict as from_dict
sage: F = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: f = from_dict(F.element_class, F, {"a": 3, "b": 5}); f.check(); f
map: a -> 3, b -> 5
sage: f.parent() is F
True
sage: f.is_immutable()
True
Creates a FiniteSetMap from a list
Warning
no check is performed !
TESTS:
sage: from sage.sets.finite_set_map_cy import FiniteSetMap_Set_from_list as from_list
sage: F = FiniteSetMaps(["a", "b"], [3, 4, 5])
sage: f = from_list(F.element_class, F, [0,2]); f.check(); f
map: a -> 3, b -> 5
sage: f.parent() is F
True
sage: f.is_immutable()
True
Returns the fibers of the function f on the finite set domain
INPUT:
OUTPUT:
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 to f.
Returns the fibers of the function f on the finite set domain
It is the same as fibers() except that one can pass extra argument for f (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}}