Source code for stallings_graphs.partial_injections_misc
# -*- coding: utf-8 -*-
r"""
The methods for the class ``PartialInjection`` use a number of ancillary functions.
We have the functions
- ``is_valid_partial_injection``, to check whether a list represents a valid partial injection
- ``number_of_partial_injections_list``, to compute the number of partial injections of a given size.
AUTHOR:
- Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr> (2018-06-09): initial version
"""
from sage.rings.integer_ring import ZZ
from sage.misc.cachefunc import cached_function
[docs]def is_valid_partial_injection(L):
r"""
Return whether a list represents a ``PartialInjection``.
``L`` is expected to be a list. It properly defines a ``PartialInjection`` if its entries are
either ``None`` or in `[0..n-1]`, where `n` is the length of ``L``, and if none of the integer entries is repeated.
INPUT:
- ``L`` -- List
OUTPUT:
- boolean
EXAMPLES::
sage: from stallings_graphs.partial_injections_misc import is_valid_partial_injection
sage: L = [3,1,4,None,2]
sage: is_valid_partial_injection(L)
True
::
sage: L = [3,1,5,None,None,1]
sage: is_valid_partial_injection(L)
False
.. WARNING::
This test is performed when a ``PartialInjection`` is defined. As a stand-alone function,
this is intended to be used when one does not want to attempt to define a
``PartialInjection`` if the list is not valid.
"""
q = L[:]
n = len(q)
b1 = all((0 <= i) and (i < n) for i in q if not (i==None))
for i in range(n):
if q[i] == None:
q[i] = -1
#
q.sort()
b2 = all((q[i] == -1) or not (q[i] == q[i+1]) for i in range(n-1))
return b1 and b2
[docs]@cached_function
def number_of_partial_injections_list(n):
r"""
Return the list of the numbers of partial injections on `0, 1, 2,..., n-1`.
The input integer is expected to be positive. A ``ValueError`` is raised otherwise.
INPUT:
- ``n`` -- integer
OUTPUT:
- a List of length `n`
EXAMPLES::
sage: from stallings_graphs.partial_injections_misc import number_of_partial_injections_list
sage: number_of_partial_injections_list(7)
[1, 2, 7, 34, 209, 1546, 13327]
ALGORITHM:
The algorithm implements a recurrence relation described in [BNW2008]_.
"""
if n == 0:
raise ValueError("the argument must be greater than 0")
elif n == 1:
P = [ZZ(1)]
elif n == 2:
P = [ZZ(1),ZZ(2)]
else:
P = [ZZ(1),ZZ(2)]
for t in range(2, n):
P.append(2 * t * P[-1] - (t - 1)**2 * P[-2])
return P