Ancillary functions about partial injections¶
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 injectionnumber_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
-
stallings_graphs.partial_injections_misc.
is_valid_partial_injection
(L)[source]¶ Return whether a list represents a
PartialInjection
.L
is expected to be a list. It properly defines aPartialInjection
if its entries are eitherNone
or in \([0..n-1]\), where \(n\) is the length ofL
, 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 aPartialInjection
if the list is not valid.
-
stallings_graphs.partial_injections_misc.
number_of_partial_injections_list
(n)[source]¶ 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].