Data structures for maps between finite sets

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

TESTS:

sage: fs = FiniteSetMaps(3)([1, 0, 2])
sage: TestSuite(fs).run()
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

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()
class sage.sets.finite_set_map_cy.FiniteSetMap_MN

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:

  • m is stored in self.parent()._m
  • n is stored in self.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 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
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 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'}}
getimage(i)

Returns the image of i by self

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 as j in self

Warning

self must be mutable; otherwise an exception is raised.

INPUT:

  • i, j – two object‘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 domain
  • parent._n contains the cardinality of the codomain
  • parent._unrank_domain and parent._rank_domain is a pair of reciprocal rank and unrank functions beween the domain and range(parent._m).
  • parent._unrank_codomain and parent._rank_codomain is a pair of reciprocal rank and unrank functions beween the codomain and range(parent._n).
classmethod from_dict(parent, d)

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
classmethod from_list(parent, lst)

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
getimage(i)

Returns the image of i by self

INPUT:

  • i – an int

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']
image_set()

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'}
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')]

TESTS:

sage: all(F.from_dict(dict(f.items())) == f for f in F)
True
setimage(i, j)

Set the image of i as j in self

Warning

self must be mutable otherwise an exception is raised.

INPUT:

  • i, j – two object‘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

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
sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_dict(cls, parent, d)

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
sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_list(cls, parent, lst)

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
sage.sets.finite_set_map_cy.fibers(f, domain)

Returns the fibers of the function f on the finite set domain

INPUT:

  • f – a function or callable
  • domain – a finite iterable

OUTPUT:

  • a dictionary d such that d[y] is the set of all x in domain such that f(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 to f.

sage.sets.finite_set_map_cy.fibers_args(f, domain, *args, **opts)

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}}

Previous topic

Maps between finite sets

Next topic

Integer Range

This Page