# 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])
```
```>>> 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: f1 = M(lambda c: ord(c)-94); f1
map: a -> 3, b -> 4
```
```>>> from sage.all import *
>>> f1 = M(lambda c: ord(c)-Integer(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
```
```>>> 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: f1 == f2
True
```
```>>> 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: list(f2)
[0, 1]
```
```>>> 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: f3 = M._from_list_([0, 1]); f3
map: a -> 3, b -> 4
sage: f1 == f3
True
```
```>>> 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[source]#

Maps from `range(n)` to itself.

`FiniteSetMap_MN` for assumptions on the parent

class sage.sets.finite_set_map_cy.FiniteSetEndoMap_Set[source]#

Maps from a set to itself

`FiniteSetMap_Set` for assumptions on the parent

class sage.sets.finite_set_map_cy.FiniteSetMap_MN[source]#

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()[source]#

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()[source]#

Returns the codomain of `self`

EXAMPLES:

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

Returns the domain of `self`

EXAMPLES:

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

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
```
```>>> 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)[source]#

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)
```
```>>> 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()[source]#

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}
```
```>>> 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()[source]#

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)]
```
```>>> 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)[source]#

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]
```
```>>> 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[source]#

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)[source]#

Creates a `FiniteSetMap` from a dictionary

Warning

no check is performed !

classmethod from_list(t, parent, lst)[source]#

Creates a `FiniteSetMap` from a list

Warning

no check is performed !

getimage(i)[source]#

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']
```
```>>> 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()[source]#

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'}
```
```>>> 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()[source]#

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')]
```
```>>> 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)[source]#

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
```
```>>> 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)[source]#

Creates a `FiniteSetMap` from a dictionary

Warning

no check is performed !

sage.sets.finite_set_map_cy.FiniteSetMap_Set_from_list(t, parent, lst)[source]#

Creates a `FiniteSetMap` from a list

Warning

no check is performed !

sage.sets.finite_set_map_cy.fibers(f, domain)[source]#

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

`fibers_args()` if one needs to pass extra arguments to `f`.

sage.sets.finite_set_map_cy.fibers_args(f, domain, *args, **opts)[source]#

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