The class PartialInjection
¶
The class PartialInjection
is meant to represent partial injections on a set of the form \([0..n-1]\).
The representation of a PartialInjection
is the list of images of \(0,\dots,n-1\), in that order, with None
in places where the partial injection is not defined.
Methods implemented in this file:
- definition of a
PartialInjection
from its list of images - random instance
size
– the length of the list of images (that is, the integer \(n\) mentioned above)domain_size
– the number of entries different fromNone
inverse_partial_injection
is_permutation
orbit_decomposition
EXAMPLES:
sage: from stallings_graphs import PartialInjection
sage: L = [0,3,None,2,4,None,5,1]
sage: p = PartialInjection(L)
sage: p
A partial injection of size 8, whose domain has size 6
sage: pinj = PartialInjection.random_instance(10)
sage: pinj # random
A partial injection of size 10, whose domain has size 7
AUTHOR:
- Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>: initial version (2018-11-26)
-
class
stallings_graphs.partial_injections.
PartialInjection
(list_of_images, check=False)[source]¶ Bases:
sage.structure.sage_object.SageObject
Define the class
PartialInjection
.The representation of a
PartialInjection
is a list of length \(n\), whose entries are either elements of \([0..n-1]\) without any repetition, orNone
(the list of images of the elements of \([0..n-1]\)). The integer \(n\) is seen as the size of thePartialInjection
.A
PartialInjection
can be created from- a list (its list of images)
or
- a random instance.
EXAMPLES
sage: from stallings_graphs import PartialInjection sage: L = [0,3,None,2,4,None] sage: p = PartialInjection(L) sage: p A partial injection of size 6, whose domain has size 4
sage: PartialInjection.random_instance(1000) # random A partial injection of size 1000, whose domain has size 969
-
domain_size
()[source]¶ Return the size of the domain of this
PartialInjection
.Computes the size of the domain of this partial injection. If it has size \(n\), its domain size is the number of elements of \([0..n-1]\) with an image, that is, \(n - \ell\), where \(\ell\) is the number of
None
.INPUT:
self
–PartialInjection
OUTPUT:
- integer
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: L = [0,3,None,2,4,None] sage: p = PartialInjection(L) sage: p.domain_size() 4
-
inverse_partial_injection
()[source]¶ Return the inverse of a
PartialInjection
.INPUT:
self
–PartialInjection
OUTPUT:
- a
PartialInjection
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: p = PartialInjection([6, None, 5, 0, 11, 2, None, 3, 9, 1, 7, 10]) sage: q = p.inverse_partial_injection() sage: q._list_of_images [3, 9, 5, 7, None, 2, 0, 10, None, 8, 11, 4]
-
is_permutation
()[source]¶ Return whether whether a
PartialInjection
is a permutation.A partial injection is a permutation if and only if its domain size is equal to its size.
INPUT:
self
–PartialInjection
OUTPUT:
- boolean
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: p = PartialInjection([6, None, 5, 0, 11, 2, None, 3, 9, 1, 7, 10]) sage: p.is_permutation() False
sage: p = PartialInjection([6, 4, 5, 0, 11, 2, 8, 3, 9, 1, 7, 10]) sage: p.is_permutation() True
-
orbit_decomposition
()[source]¶ Return the orbit decomposition of a
PartialInjection
.A partial injection admits a unique decomposition into its \(\textit{maximal orbits}\): a list of sequences and a list of cycles. The particular case of a permutation is that where each orbit is a cycle.
INPUT:
self
–PartialInjection
OUTPUT:
- List of 2 lists
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: p = PartialInjection([6, None, 5, 0, 11, 2, None, 3, 9, 1, 7, 10]) sage: p.orbit_decomposition() ([[4, 11, 10, 7, 3, 0, 6], [8, 9, 1]], [[2, 5]])
-
static
random_instance
(size, statistics=False)[source]¶ Returns a randomly chosen
PartialInjection
of givensize
.size
is expected to be a positive integer. Ifstatistics
is set toTrue
, the method also returns the number of orbits of the partial injection that are sequences. This number is expected to be asymptotically equivalent to \(\sqrt n\), with standard deviation \(o(\sqrt n)\), where \(n\) is equal tosize
.INPUT:
size
– integerstatistics
– boolean
OUTPUT:
- an object of the class
PartialInjection
ifstatistics = False
; and a pair of an integer and an object of classPartialInjection
otherwise
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: rand_inj = PartialInjection.random_instance(10) sage: rand_inj._list_of_images # random [0, 4, 2, None, 3, 9, 7, 8, 6, None]
sage: rand_inj = PartialInjection.random_instance(10) sage: rand_inj._list_of_images # random [2, 4, 6, 0, 3, None, 9, 5, None, None]
ALGORITHM:
Tha algorithm implemented here is that in [BNW2008]. It performs in linear time, except for a preprocessing which is cached.
-
size
()[source]¶ Return the size of this
PartialInjection
.The size of a
PartialInjection
is the length of the list that represents it.INPUT:
self
–PartialInjection
OUTPUT:
- integer
EXAMPLES:
sage: from stallings_graphs import PartialInjection sage: L = [0,3,None,2,4,None] sage: p = PartialInjection(L) sage: p.size() 6