# -*- coding: utf-8 -*-
r"""
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:
- Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>: initial version (2018-11-26)
"""
from sage.structure.sage_object import SageObject
from sage.misc.prandom import shuffle, randint
from random import randrange
import itertools
from stallings_graphs.partial_injections_misc import *
[docs]class PartialInjection(SageObject):
r"""
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
"""
def __init__(self, list_of_images, check=False):
r"""
Create a ``PartialInjection`` by specifying the list of images of `[0..n-1]`.
This list ``list_of_images``, if it has length `n`, is expected to have entries that are either
elements of `[0..n-1]`, without any repetition, or ``None``. This property is verified
in ``__init__`` if ``check`` is set to ``True``.
The empty list is acceptable: it represents the (unique) map from the empty
set into itself.
INPUT:
- ``list_of_images`` -- list
- ``check``-- boolean
OUTPUT:
- an object of class ``PartialInjection``
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: L = []
sage: p = PartialInjection(L)
sage: p
A partial injection of size 0, whose domain has size 0
"""
if check == True:
if not isinstance(list_of_images, list):
raise TypeError('list_of_images(={}) must be of type list'.format(list_of_images))
if not is_valid_partial_injection(list_of_images):
raise ValueError('list_of_images(={}) does not represent a partial injection from [0..{}] into itself'.format(list_of_images, len(list_of_images) - 1))
#
self._list_of_images = list_of_images
def __repr__(self):
r"""
Return a description of this ``PartialInjection``.
The description consists of its size and the size of its domain (that is:
the number of entries different from ``None``).
INPUT:
- ``self`` -- an object of class ``PartialInjection``.
OUTPUT:
- a sentence describing the corresponding partial injection.
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
"""
return 'A partial injection of size {}, whose domain has size {}'.format(self.size(), self.domain_size())
def __eq__(self, other):
r"""
Return whether these two ``PartialInjection`` objects are equal.
``other`` is expected to be, like ``self``, an object of class ``PartialInjection``, a ``ValueError``is raised
if that is not the case. Two ``PartialInjection``objects are equal when their ``list_of_images`` are equal
INPUT:
- ``self`` -- ``PartialInjection``
- ``other`` -- `PartialInjection``
OUTPUT:
- boolean
EXAMPLES ::
sage: from stallings_graphs import PartialInjection
sage: p1 = PartialInjection([1,2,None,4,5,3])
sage: p2 = PartialInjection([0,3,4,None,None,None])
sage: p1 == p2
False
::
sage: p1 = PartialInjection([])
sage: p2 = PartialInjection([None])
sage: p1 == p2
False
::
sage: p1 = PartialInjection([None])
sage: p2 = PartialInjection([None,None])
sage: p1 == p2
False
"""
b = isinstance(other, PartialInjection)
if not b:
print('the second argument is not a PartialInjection')
return False
return (self._list_of_images == other._list_of_images)
[docs] def size(self):
r"""
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
"""
return len(self._list_of_images)
[docs] def domain_size(self):
r"""
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
"""
p = self._list_of_images
return len(p) - p.count(None)
[docs] def inverse_partial_injection(self):
r"""
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]
"""
p = self._list_of_images
q = [None for _ in range(len(p))]
for i,j in enumerate(p):
if j != None:
q[j] = i
return PartialInjection(q)
[docs] def is_permutation(self):
r"""
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
"""
return self.size() == self.domain_size()
[docs] def orbit_decomposition(self):
r"""
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]])
"""
p = self._list_of_images
sequence_list = []
cycle_list = []
d = {}
deja_vus = set()
for i in range(len(p)):
if not (i in deja_vus):
d[i] = [i]
deja_vus.add(i)
j = p[i]
while (j != None) and not (j in d.keys()):
d[i].append(j)
deja_vus.add(j)
j = p[j]
if j == i:
cycle_list.append(d[i])
del d[i]
else:
if j in d.keys():
d[i].extend(d[j])
del d[j]
sequence_list = [d[i] for i in d.keys()]
return sequence_list, cycle_list
[docs] @staticmethod
def random_instance(size,statistics=False):
r"""
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.
"""
# first: produce two lists, namely the list of sizes of cycle
# components and the list of sizes of stick components
n0 = size
cycles = []
sticks = []
Inj = number_of_partial_injections_list(size + 1)
while size > 0:
# compute the size k of a component
dice = randint(1,Inj[size])
k = 1
T = 1
S = 2 * Inj[size - 1]
while dice > S:
T = T * (size - k)
k = k + 1
S = S + (k + 1) * T * Inj[size - k]
new_dice = randrange(k + 1)
if new_dice == k:
cycles.append(k)
else:
sticks.append(k)
size = size - k
# when the while loop is over, we have two lists: the sizes of cycle components and the sizes of stick components.
# Now turn the lists of sizes of cycles and sticks to a scheme of a permutation
schema_of_rand_inj = []
it = itertools.count(0)
b = next(it)
for a in cycles:
for _ in range(a-1):
schema_of_rand_inj.append(next(it))
schema_of_rand_inj.append(b)
b = next(it)
for a in sticks:
for _ in range(a-1):
schema_of_rand_inj.append(next(it))
schema_of_rand_inj.append(None)
b = next(it)
# Finally, randomly label the places in this partial injection
R = list(range(n0))
# R = [i for i in range(n0)]
shuffle(R)
rand_inj = [0 for _ in range(n0)]
for i,a in enumerate(schema_of_rand_inj):
if a is None:
rand_inj[R[i]] = None
else:
rand_inj[R[i]] = R[a]
if statistics:
return len(sticks), PartialInjection(rand_inj)
else:
return PartialInjection(rand_inj)