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.Lis expected to be a list. It properly defines aPartialInjectionif its entries are eitherNoneor 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
PartialInjectionis defined. As a stand-alone function, this is intended to be used when one does not want to attempt to define aPartialInjectionif 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
ValueErroris 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].