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) 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.

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'}}
True
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 between the domain and range(parent._m).

  • parent._unrank_codomain and parent._rank_codomain is a pair of reciprocal rank and unrank functions between the codomain and range(parent._n).

classmethod from_dict(t, parent, d)

Creates a FiniteSetMap from a dictionary

Warning

no check is performed !

classmethod from_list(t, parent, lst)

Creates a FiniteSetMap from a list

Warning

no check is performed !

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

Creates a FiniteSetMap from a dictionary

Warning

no check is performed !

sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_list(t, parent, lst)

Creates a FiniteSetMap from a list

Warning

no check is performed !

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