matchpy.utils module¶
This module contains various utility functions.

fixed_integer_vector_iter
(max_vector: Tuple[int, ...], vector_sum: int) → Iterator[Tuple[int, ...]]¶ Return an iterator over the integer vectors which
 are componentwise less than or equal to max_vector, and
 are nonnegative, and where
 the sum of their components is exactly vector_sum.
The iterator yields the vectors in lexicographical order.
Examples
List all vectors that are between
(0, 0)
and(2, 2)
componentwise, where the sum of components is 2:>>> vectors = list(fixed_integer_vector_iter([2, 2], 2)) >>> vectors [(0, 2), (1, 1), (2, 0)] >>> list(map(sum, vectors)) [2, 2, 2]
Parameters:  max_vector – Maximum vector for the iteration. Every yielded result will be less than or equal to this componentwise.
 vector_sum – Every iterated vector will have a component sum equal to this value.
Yields: All nonnegative vectors that have the given sum and are not larger than the given maximum.
Raises: ValueError
– If vector_sum is negative.

weak_composition_iter
(n: int, num_parts: int) → Iterator[Tuple[int, ...]]¶ Yield all weak compositions of integer n into num_parts parts.
Each composition is yielded as a tuple. The generated partitions are orderdependant and not unique when ignoring the order of the components. The partitions are yielded in lexicographical order.
Example
>>> compositions = list(weak_composition_iter(5, 2)) >>> compositions [(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)]
We can easily verify that all compositions are indeed valid:
>>> list(map(sum, compositions)) [5, 5, 5, 5, 5, 5]
The algorithm was adapted from an answer to this Stackoverflow question.
Parameters:  n – The integer to partition.
 num_parts – The number of parts for the combination.
Yields: All nonnegative tuples that have the given sum and size.
Raises: ValueError
– If n or num_parts are negative.

commutative_sequence_variable_partition_iter
(values: multiset.Multiset, variables: List[matchpy.utils.VariableWithCount]) → Iterator[Dict[str, multiset.Multiset]]¶ Yield all possible variable substitutions for given values and variables.
Note
The results are not yielded in any particular order because the algorithm uses dictionaries. Dictionaries until Python 3.6 do not keep track of the insertion order.
Example
For a subject like
fc(a, a, a, b, b, c)
and a pattern likef(x__, y___, y___)
one can define the following input parameters for the partitioning:>>> x = VariableWithCount(name='x', count=1, minimum=1, default=None) >>> y = VariableWithCount(name='y', count=2, minimum=0, default=None) >>> values = Multiset('aaabbc')
Then the solutions are found (and sorted to get a unique output):
>>> substitutions = commutative_sequence_variable_partition_iter(values, [x, y]) >>> as_strings = list(str(Substitution(substitution)) for substitution in substitutions) >>> for substitution in sorted(as_strings): ... print(substitution) {x ↦ {a, a, a, b, b, c}, y ↦ {}} {x ↦ {a, a, a, c}, y ↦ {b}} {x ↦ {a, b, b, c}, y ↦ {a}} {x ↦ {a, c}, y ↦ {a, b}}
Parameters:  values – The multiset of values which are partitioned and distributed among the variables.
 variables – A list of the variables to distribute the values among. Each variable has a name, a count of how many times it occurs and a minimum number of values it needs.
Yields: Each possible substitutions that is a valid partitioning of the values among the variables.

get_short_lambda_source
(lambda_func: function) → Optional[str]¶ Return the source of a (short) lambda function. If it’s impossible to obtain, return
None
.The source is returned without the
lambda
and signature parts:>>> get_short_lambda_source(lambda x, y: x < y) 'x < y'
This should work well for most lambda definitions, however for multiline or highly nested lambdas, the source extraction might not succeed.
Parameters: lambda_func – The lambda function. Returns: The source of the lambda function without its signature.

solve_linear_diop
(total: int, *coeffs) → Iterator[Tuple[int, ...]]¶ Yield nonnegative integer solutions of a linear Diophantine equation of the format \(c_1 x_1 + \dots + c_n x_n = total\).
If there are at most two coefficients,
base_solution_linear()
is used to find the solutions. Otherwise, the solutions are found recursively, by reducing the number of variables in each recursion: Compute \(d := gcd(c_2, \dots , c_n)\)
 Solve \(c_1 x + d y = total\)
 Recursively solve \(c_2 x_2 + \dots + c_n x_n = y\) for each solution for \(y\)
 Combine these solutions to form a solution for the whole equation
Parameters:  total – The constant of the equation.
 *coeffs – The coefficients \(c_i\) of the equation.
Yields: The nonnegative integer solutions of the equation as a tuple \((x_1, \dots, x_n)\).

generator_chain
(initial_data: T, *factories) → Iterator[T]¶ Chain multiple generators together by passing results from one to the next.
This helper function allows to create a chain of generator where each generator is constructed by a factory that gets the data yielded by the previous generator. So each generator can generate new data dependant on the data yielded by the previous one. For each data item yielded by a generator, a new generator is constructed by the next factory.
Example
Lets say for every number from 0 to 4, we want to count up to that number. Then we can do something like this using list comprehensions:
>>> [i for n in range(1, 5) for i in range(1, n + 1)] [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]
You can use this function to achieve the same thing:
>>> list(generator_chain(5, lambda n: iter(range(1, n)), lambda i: iter(range(1, i + 1)))) [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]
The advantage is, that this is independent of the number of dependant generators you have. Also, this function does not use recursion so it is safe to use even with large generator counts.
Parameters:  initial_data – The initial data that is passed to the first generator factory.
 *factories – The generator factories. Each of them gets passed its predecessors data and has to return an iterable. The data from this iterable is passed to the next factory.
Yields: Every data item yielded by the generators of the final factory.

class
cached_property
(getter, slot=None)¶ Bases:
property
Property with caching.
An extension of the builtin
property
, that caches the value after the first access. This is useful in case the computation of the property value is expensive.Use it just like a regular property decorator. Cached properties cannot have a setter.
Example
First, create a class with a cached property:
>>> class MyClass: ... @cached_property ... def my_property(self): ... print('my_property called') ... return 42 >>> instance = MyClass()
Then, access the property and get the computed value:
>>> instance.my_property my_property called 42
Now the result is cached and the original method will not be called again:
>>> instance.my_property 42

__init__
(getter, slot=None)¶ Use it as a decorator:
>>> class MyClass: ... @cached_property ... def my_property(self): ... return 42
The slot argument specifies a class slot to use for caching the property. You should use the
slot_cached_property
decorator instead as that is more convenient.Parameters:  getter – The getter method for the property.
 slot – Optional slot to use for the cached value. Only relevant in classes that use slots.
Use
slot_cached_property
instead.
Returns: The wrapped
property
with caching.


slot_cached_property
(slot)¶ Property with caching for classes with slots.
This is a wrapper around
cached_property
to be used with classes that have slots. It provides an extension of the builtinproperty
, that caches the value in a slot after the first access. You need to specify which slot to use for the cached value.Example
First, create a class with a cached property and a slot to hold the cached value:
>>> class MyClass: ... __slots__ = ('_my_cached_property', ) ... ... @slot_cached_property('_my_cached_property') ... def my_property(self): ... print('my_property called') ... return 42 ... >>> instance = MyClass()
Then, access the property and get the computed value:
>>> instance.my_property my_property called 42
Now the result is cached and the original method will not be called again:
>>> instance.my_property 42
Parameters: slot – The name of the classes slot to use for the cached value. Returns: The wrapped cached_property
.

extended_euclid
(a: int, b: int) → Tuple[int, int, int]¶ Extended Euclidean algorithm that computes the Bézout coefficients as well as \(gcd(a, b)\)
Returns
x, y, d
where x and y are a solution to \(ax + by = d\) and \(d = gcd(a, b)\). x and y are a minimal pair of Bézout’s coefficients.See Extended Euclidean algorithm or Bézout’s identity for more information.
Example
Compute the Bézout coefficients and GCD of 42 and 12:
>>> a, b = 42, 12 >>> x, y, d = extended_euclid(a, b) >>> x, y, d (1, 3, 6)
Verify the results:
>>> import math >>> d == math.gcd(a, b) True >>> a * x + b * y == d True
Parameters:  a – The first integer.
 b – The second integer.
Returns: A tuple with the Bézout coefficients and the greatest common divider of the arguments.

base_solution_linear
(a: int, b: int, c: int) → Iterator[Tuple[int, int]]¶ Yield solutions for a basic linear Diophantine equation of the form \(ax + by = c\).
First, the equation is normalized by dividing \(a, b, c\) by their gcd. Then, the extended Euclidean algorithm (
extended_euclid()
) is used to find a base solution \((x_0, y_0)\).All nonnegative solutions are generated by using that the general solution is \((x_0 + b t, y_0  a t)\). Because the base solution is one of the minimal pairs of Bézout’s coefficients, for all nonnegative solutions either \(t \geq 0\) or \(t \leq 0\) must hold. Also, all the nonnegative solutions are consecutive with respect to \(t\).
Hence, by adding or subtracting \(a\) resp. \(b\) from the base solution, all nonnegative solutions can be efficiently generated.
Parameters:  a – The first coefficient of the equation.
 b – The second coefficient of the equation.
 c – The constant of the equation.
Yields: Each nonnegative integer solution of the equation as a tuple
(x, y)
.Raises: ValueError
– If any of the coefficients is not a positive integer.