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, .., 2}
Returns the domain of self
EXAMPLES:
sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).domain()
{0, .., 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: list.index(x): x not in list
sage: with fs.clone() as fs3:
... fs3.setimage(1, 4)
Traceback (most recent call last):
...
ValueError: list.index(x): x 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])
{16: {4}, 1: {1, -1}, 4: {2}, 9: {3, -3}}
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)
{16: {4}, 1: {1, -1}, 4: {2}, 9: {3, -3}}