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

sage: M = FiniteSetMaps(["a", "b"], [3, 4, 5])

Python

>>> from sage.all import *
>>> M = FiniteSetMaps(["a", "b"], [Integer(3), Integer(4), Integer(5)])

The map can then be constructed either from a function:

Sage

sage: f1 = M(lambda c: ord(c)-94); f1
map: a -> 3, b -> 4

Python

>>> from sage.all import *
>>> f1 = M(lambda c: ord(c)-Integer(94)); f1
map: a -> 3, b -> 4

or from a dictionary:

Sage

sage: f2 = M.from_dict({'a':3, 'b':4}); f2
map: a -> 3, b -> 4

Python

>>> from sage.all import *
>>> f2 = M.from_dict({'a':Integer(3), 'b':Integer(4)}); f2
map: a -> 3, b -> 4

The two created maps are equal:

Sage

sage: f1 == f2
True

Python

>>> from sage.all import *
>>> 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

sage: list(f2)
[0, 1]

Python

>>> from sage.all import *
>>> 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

sage: f3 = M._from_list_([0, 1]); f3
map: a -> 3, b -> 4
sage: f1 == f3
True

Python

>>> from sage.all import *
>>> f3 = M._from_list_([Integer(0), Integer(1)]); f3
map: a -> 3, b -> 4
>>> f1 == f3
True

AUTHORS:

• Florent Hivert

class sage.sets.finite_set_map_cy.FiniteSetEndoMap_N

Bases: FiniteSetMap_MN

Map from range(n) to itself.

See also

FiniteSetMap_MN for assumptions on the parent

class sage.sets.finite_set_map_cy.FiniteSetEndoMap_Set

Bases: FiniteSetMap_Set

Map from a set to itself.

See also

FiniteSetMap_Set for assumptions on the parent

class sage.sets.finite_set_map_cy.FiniteSetMap_MN

Bases: ClonableIntArray

Data structure for maps from range(m) to range(n).

We assume that the parent given as argument is such that:

• m – stored in self.parent()._m

• n – stored in self.parent()._n

• the domain is in self.parent().domain()

• the codomain is in self.parent().codomain()

check()

Perform 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()

Return the codomain of self.

EXAMPLES:

Sage

sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).codomain()
{0, 1, 2}

Python

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)]).codomain()
{0, 1, 2}

domain()

Return the domain of self.

EXAMPLES:

Sage

sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).domain()
{0, 1, 2, 3}

Python

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)]).domain()
{0, 1, 2, 3}

fibers()

Return 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

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

Python

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)]).fibers()
{0: {1}, 1: {0, 3}, 2: {2}}
>>> F = FiniteSetMaps(["a", "b", "c"])
>>> F.from_dict({"a": "b", "b": "a", "c": "b"}).fibers() == {'a': {'b'}, 'b': {'a', 'c'}}
True

getimage(i)

Return the image of i by self.

INPUT:

• i – any object

Note

if you need speed, please use instead _getimage()

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> fs = FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)])
>>> fs.getimage(Integer(0)), fs.getimage(Integer(1)), fs.getimage(Integer(2)), fs.getimage(Integer(3))
(1, 0, 2, 1)

image_set()

Return the image set of self.

EXAMPLES:

Sage

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}

Python

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)]).image_set()
{0, 1, 2}
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(0), Integer(1)]).image_set()
{0, 1}

items()

The items of self.

Return the list of the ordered pairs (x, self(x))

EXAMPLES:

Sage

sage: FiniteSetMaps(4, 3)([1, 0, 2, 1]).items()
[(0, 1), (1, 0), (2, 2), (3, 1)]

Python

>>> from sage.all import *
>>> FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(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

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]

Python

>>> from sage.all import *
>>> fs = FiniteSetMaps(Integer(4), Integer(3))([Integer(1), Integer(0), Integer(2), Integer(1)])
>>> fs2 = copy(fs)
>>> fs2.setimage(Integer(2), Integer(1))
>>> fs2
[1, 0, 1, 1]
>>> with fs.clone() as fs3:
...     fs3.setimage(Integer(0), Integer(2))
...     fs3.setimage(Integer(1), Integer(2))
>>> fs3
[2, 2, 2, 1]

class sage.sets.finite_set_map_cy.FiniteSetMap_Set

Bases: 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)

Create a FiniteSetMap from a dictionary.

Warning

no check is performed !

classmethod from_list(t, parent, lst)

Create a FiniteSetMap from a list.

Warning

no check is performed !

getimage(i)

Return the image of i by self.

INPUT:

• i – integer

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = FiniteSetMaps(["a", "b", "c", "d"], ["u", "v", "w"])
>>> fs = F._from_list_([Integer(1), Integer(0), Integer(2), Integer(1)])
>>> list(map(fs.getimage, ["a", "b", "c", "d"]))
['v', 'u', 'w', 'v']

image_set()

Return the image set of self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = FiniteSetMaps(["a", "b", "c"])
>>> sorted(F.from_dict({"a": "b", "b": "a", "c": "b"}).image_set())
['a', 'b']
>>> F = FiniteSetMaps(["a", "b", "c"])
>>> F(lambda x: "c").image_set()
{'c'}

items()

The items of self.

Return the list of the couple (x, self(x))

EXAMPLES:

Sage

sage: F = FiniteSetMaps(["a", "b", "c"])
sage: F.from_dict({"a": "b", "b": "a", "c": "b"}).items()
[('a', 'b'), ('b', 'a'), ('c', 'b')]

Python

>>> from sage.all import *
>>> F = FiniteSetMaps(["a", "b", "c"])
>>> 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

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

Python

>>> from sage.all import *
>>> F = FiniteSetMaps(["a", "b", "c", "d"], ["u", "v", "w"])
>>> fs = F(lambda x: "v")
>>> fs2 = copy(fs)
>>> fs2.setimage("a", "w")
>>> fs2
map: a -> w, b -> v, c -> v, d -> v
>>> with fs.clone() as fs3:
...     fs3.setimage("a", "u")
...     fs3.setimage("c", "w")
>>> fs3
map: a -> u, b -> v, c -> w, d -> v

sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_dict(t, parent, d)

Create a FiniteSetMap from a dictionary.

Warning

no check is performed !

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

Create a FiniteSetMap from a list.

Warning

no check is performed !

sage.sets.finite_set_map_cy.fibers(f, domain)

Return 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

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

Python

>>> from sage.all import *
>>> from sage.sets.finite_set_map_cy import fibers, fibers_args
>>> fibers(lambda x: Integer(1), [])
{}
>>> fibers(lambda x: x**Integer(2), [-Integer(1), Integer(2), -Integer(3), Integer(1), Integer(3), Integer(4)])
{1: {1, -1}, 4: {2}, 9: {3, -3}, 16: {4}}
>>> fibers(lambda x: Integer(1),   [-Integer(1), Integer(2), -Integer(3), Integer(1), Integer(3), Integer(4)])
{1: {1, 2, 3, 4, -3, -1}}
>>> fibers(lambda x: Integer(1), [Integer(1),Integer(1),Integer(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)

Return 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

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

Python

>>> from sage.all import *
>>> from sage.sets.finite_set_map_cy import fibers_args
>>> fibers_args(operator.pow, [-Integer(1), Integer(2), -Integer(3), Integer(1), Integer(3), Integer(4)], Integer(2))
{1: {1, -1}, 4: {2}, 9: {3, -3}, 16: {4}}