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 from None
  • 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:

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, or None (the list of images of the elements of \([0..n-1]\)). The integer \(n\) is seen as the size of the PartialInjection.

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:

  • selfPartialInjection

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:

  • selfPartialInjection

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:

  • selfPartialInjection

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:

  • selfPartialInjection

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 given size.

size is expected to be a positive integer. If statistics is set to True, 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 to size.

INPUT:

  • size – integer
  • statistics – boolean

OUTPUT:

  • an object of the class PartialInjection if statistics = False; and a pair of an integer and an object of class PartialInjection 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:

  • selfPartialInjection

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