2
\$\begingroup\$

Introduction

I have implemented a generalization to the inclusion-exclusion principle, which extends the principle from sets to more general objects. In short the principle calculates the left by doing the calculation on the right

enter image description here

enter image description here

In order to extend this to general objects, these objects need to have some structure (some defining property). They need to have a concept of intersection (what it two objects have in common) and lastly a notion of cardinality (size or in pythons terms the length). The symbol for intersection is ∩ and for cardinality | | is used.

So this code does precisely that. It creates objects which have a notion of intersection, cardinality and then uses the inclusion-exclusion principle to calculate the size (cardinality) of their union (|A U B U .. |).

Wanted feedback

My code works, but I do get some typing hint errors as I am unsure on how to annotate the IEP class. So feedback on how to implement proper typing hints is more than welcome.

Speaking of IEP, I feel my whole construction of objects is contrived. What I want is some generic metaclass, which again produces IEP objects which has a set intersection and cardinality. This is what the make_IEP do, but again, pushing a class inside a function seems counter-intuitive.

Code

utilities.py

from collections.abc import Iterable, Callable
from typing import Any, TypeVar, Tuple, Union

import functools
import itertools

_T = TypeVar("_T")
_S = TypeVar("_S")

@functools.cache
def reduce_w_cache(function: Callable[[_T, _S], _T], sequence: Iterable[_S]) -> _S:
    """Reduces the sequence to a single number by left folding function over it

    Example:

        The easiest way to understand how reduce works is applying a tuple to it
        >>> sequence = tuple([1, 3, 5, 6, 2])
        >>> make_tuple = lambda x, y: tuple([x, y])
        >>> reduce_w_cache(make_tuple, sequence)
        ((((1, 3), 5), 6), 2)

        Similarly a right fold would look like ``(1, (3, (5, (6, 2))))``

        >>> add = lambda x, y: x + y
        >>> sum_reduce = lambda x: reduce_w_cache(add, x)
        >>> reduce_w_cache(add, sequence)
        17

        Understanding how this works is as easy as replacing , with + in the
        example above

            reduce_w_cache(add, sequence) = ((((1 + 3) + 5) + 6) + 2) = 17

        Let us test if the caching works. We first save how many misses we
        have, where a miss corresponds to a value being added to the cache. We
        will then perform some lookups and study how many values were cached.

        >>> repeat_reduce = lambda fun, seqs: [reduce_w_cache(fun, tuple(s)) for s in seqs]
        >>> def values_cached(function, sequences):
        ...     initial = reduce_w_cache.cache_info().misses
        ...     repeat_reduce(function, sequences)
        ...     total = reduce_w_cache.cache_info().misses
        ...     return total - initial

        >>> test_function = lambda x, y: [x, y]
        >>> sequences = [
            [103], [103, 105], [103, 105, 107], [103, 105, 107, 109], [103, 105, 107, 109, 111]
        ]

        We are going to run ``reduce_w_cache`` with ``test_function`` over each
        element in ``sequences``. With no caching we would expect ``len - 1``
        function calls with a minimal of ``1`` for each sequence in sequences.
        Totaling to ``1 + 1 + 2 + 3 + 4 = 11`` function calls.

        However with cached values this is greatly lowered. For instance ``(103,
        105, 107)`` folds to ``(103, (105, 107))`` and the value of 
        ``(105, 107)`` is already stored in the cache.
        >>> values_cached(test_function, sequences)
        5

        No new values should be added if we lookup the same values again
        >>> values_cached(test_function, sequences)
        0

        As a sanity check let us test how many values are cached when
        we can not use previously stored values
        >>> sequences = [
            [112], [113, 114], [115, 116, 117], [118, 119, 120, 121], [118, 119, 120, 121, 122]
        ]
        >>> values_cached(test_function, sequences)
        11

        Let us double check that the number of calls really is 11. For each
        function call we wrap two elements in ``[]`` so simply counting the number
        of either ``[`` or ``]`` returns the number of function calls.
        >>> str(repeat_reduce(test_function, sequences)).count('[')
        11
    """
    *remaining, last = sequence
    if not remaining:
        return last
    return function(reduce_w_cache(function, tuple(remaining)), last)


def powerset(iterable:Iterable[Any], emptyset:bool=False, flatten:bool=True) -> Iterable[Union[Tuple[Any, ...],Iterable[Tuple[Any, ...]]]]:
    """Returns the powerset of some list without the emptyset as default

    Examples:
        >>> list(powerset([1,2,3]))
        [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

        >>> list(powerset([1,2,3], emptyset=True))
        [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

        >>> list(list(i) for i in powerset([1,2,3], flatten=False))
        [[(1,), (2,), (3,)], [(1, 2), (1, 3), (2, 3)], [(1, 2, 3)]]

        >>> list(list(i) for i in powerset([1,2,3], emptyset=True, flatten=False))
        [[()], [(1,), (2,), (3,)], [(1, 2), (1, 3), (2, 3)], [(1, 2, 3)]]
    """

    try:
        iter(iterable)
        s = list(iterable)
    except TypeError:
        if not isinstance(iterable, list):
            raise TypeError("Input must be list or iterable")
        s = iterable
    start = 0 if emptyset else 1
    powerset_ = (itertools.combinations(s, r) for r in range(start, len(s) + 1))
    return itertools.chain.from_iterable(powerset_) if flatten else powerset_


if __name__ == "__main__":
    import doctest

    doctest.testmod()

iep.py

"""
    Provides a module for the inclusion exclusion protocol
"""

from collections.abc import Callable
import functools
from typing import Annotated, Any, Union, Type

from utilities import powerset, reduce_w_cache

Structure = Annotated[
    Any,
    "An intrinsic property that defines the shape and form of our object",
]
Intersection = Annotated[
    Callable[[Structure, Structure], Structure],
    "Is a callable function that takes in two structures and returns the"
    "intersection, which is a new (smaller or equal) structure.",
]
# Defines an empty class here for typing hints
class IEP:
    def __init__(self, structure: Structure):
        self.structure = structure
        pass


Cardinality = Annotated[
    Callable[[Type[IEP]], Union[int, float]],
    "Is a callable function that returns the general concept of size for an object",
]


class ConstructorIEP:
    """Implements intersection and cardinality (len) for the IEP class"""

    def cardinality(self, x):
        return x

    def intersect(self, x, _):
        return x

    @property
    def structure(self):
        return self._structure

    @structure.setter
    def structure(self, stuff: Structure):
        self._structure = stuff
        self.len = self.cardinality(self._structure)

    def intersection(self, *others: Type[IEP]):
        if len(others) == 0:
            new_structure = self.structure
        new_structure = self.structure
        for other in others:
            new_structure = self.intersect(new_structure, other.structure)
        NewIEP = make_IEP(self.intersect, self.cardinality)
        return NewIEP(new_structure)

    def __len__(self):
        return self.len

    def __repr__(self):
        return f"IEP({self.structure})"

    def __str__(self):
        return f"{self.structure}, len={self.len}"


def make_IEP(intersect: Intersection, cardinality: Cardinality) -> Type[IEP]:
    """Creates an IEP class with a fixed intersect and cardinality"""

    class IEP(ConstructorIEP):
        def __init__(self, structure: Structure):
            self.intersect = intersect
            self.cardinality = cardinality
            self.structure = structure

    return IEP


def inclusion_exclusion_principle(
    structure_of_objects: list[Structure],
    intersection_: Intersection,
    cardinality_: Cardinality,
    cache: bool = False,
) -> int:
    """If structure_of_objects = [A, B, C, ...] this function returns |A U B U C U ...|

    The return value is calculated using the exclusion inclusion principle;
    here | | denotes the cardinality (or in Pythons words the length) of the set,
    and ∩ represents the intersection of two objects, and U representens the union.
    See the link for more information

    https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

    Args:
        structure_of_objects: A list of structures that with intersection and
                              cardinality defines an object
        intersection: A function(x, y) that returns what two object structures has
                      in common (defines x.intersection(y))
        cardinality: A function(x) that returns the size of an object (defines len(object))

    Returns:
        int: Returns the size (``len``) of the intersection of every element in ``list_of_objects``

    Examples:

        Setup for discrete sets
        >>> intersection = lambda a, b: a.intersection(b)
        >>> cardinality = len
        >>> sets = [set([])]
        >>> inclusion_exclusion_principle([{}], intersection, cardinality)
        0
        >>> inclusion_exclusion_principle([{1, 2, 3}, {1, 2, 3}], intersection, cardinality)
        3
        >>> inclusion_exclusion_principle([{1, 2, 3}, {4, 5, 6}], intersection, cardinality)
        6

        Setup for continous ranges is a bit harder as it is cumbersome to define the
        intersections between two intervals properly
        >>> def intersection(*intervals):
        ...     max_first, min_last = [f(i) for f, i in zip([max, min], zip(*intervals))]
        ...     if (min_last - max_first) >= 0:
        ...         return [max_first, min_last]
        ...     return [float("inf"), float("inf")]
        ...
        >>> cardinality = lambda a: len(range(*a))
        >>> inclusion_exclusion_principle([[0, 0]], intersection, cardinality)
        0
        >>> inclusion_exclusion_principle([[1, 2], [1, 2]], intersection, cardinality)
        1
        >>> inclusion_exclusion_principle([[0, 3], [1, 2]], intersection, cardinality)
        3
        >>> inclusion_exclusion_principle([[2, 4], [3, 5], [4, 6]], intersection, cardinality)
        4

        As a more advanced example we can use inclusion-exclusion-principle to
        find the union of all numbers divisible by 1 or more of our objects.
        Essentially solving the first project euler problem
        >>> gcd = lambda m,n: m if not n else gcd(n, m % n)
        >>> lcm = lambda a, b: abs(a * b) // gcd(a, b)
        >>> start, stop = 1, 1000
        >>> intersection = lcm
        >>> cardinality = lambda x: sum(i for i in range(start, stop) if i % x == 0)
        >>> inclusion_exclusion_principle([3, 5], intersection, cardinality)
        233168

        Of course this could have been improved by implementing a cardinality
        that runs in linear time
        >>> sum_linear = lambda start, stop: (stop + start + 1) * (stop - start) // 2
        >>> cardinality = lambda x: x * sum_linear(start//x, (stop-1)//x)
        >>> inclusion_exclusion_principle([3, 5], intersection, cardinality)
        233168
    """

    class IEP(ConstructorIEP):
        def __init__(self, structure: Structure):
            self.intersect = intersection_
            self.cardinality = cardinality_
            self.structure = structure

    list_of_objects = list(map(IEP, structure_of_objects))
    reduce = reduce_w_cache if cache else functools.reduce

    def intersect(list_of_objects: list[Type[IEP]]):
        """Finds the intersection of a list of objects according to the rules set by intersection"""

        # If the list of sets only contains one element, we are left with
        # finding the intersection of a set with itself. However, this is just
        # the set itself, because intersection retrieves the common elements.
        # Here, all elements of a set is common with itself. Hence, the
        # resulting intersection of a set with itself, is itself
        if len(list_of_objects) == 1:
            return list_of_objects[0]
        return reduce(lambda x, y: x.intersection(y), list_of_objects)

    def cardinality(obj):
        return len(obj)

    cardinality_of_union, sign = 0, 1
    # It will be easier to follow this code through an example
    # list_of_objects = [A, B, C]
    # powerset(list_of_objects, flatten=False) = [
    #       [[A], [B], [C]],
    #       [[A, B], [A, C], [B, C]],
    #       [A, B, C]]
    # ]
    for subsets_w_same_len in powerset(list_of_objects, flatten=False):
        # intersections:
        #    First pass: = [A, B, C]              # All subsets of len 1 (intersection of itself is itself)
        #   Second pass: = [A ∩ B, A ∩ C, B ∩ C]  # All subsets of len 2
        #    Final pass: = [A ∩ B ∩ C]            # All subsets of len 3
        intersections = map(intersect, subsets_w_same_len)
        # cardinalities:
        #    First pass: = [ |A|, |B|, |C| ]
        #   Second pass: = [ |A ∩ B|, |A ∩ C|, |B ∩ C| ]
        #    Final pass: = [ |A ∩ B ∩ C| ]
        cardinalities = map(cardinality, intersections)
        # cardinality_of_union:
        #    First pass: = |A| + |B| + |C|
        #   Second pass: = |A| + |B| + |C|
        #                - ( |A ∩ B| + |A ∩ C| + |B ∩ C| )
        #    Final pass: = |A| + |B| + |C|
        #                - ( |A ∩ B| + |A ∩ C| + |B ∩ C| )
        #                + ( |A ∩ B ∩ C| )
        cardinality_of_union += sign * sum(cardinalities)
        sign *= -1
    # Where
    # cardinality_of_union = |A| + |B| + |C|
    #                      - ( |A ∩ B| + |A ∩ C| + |B ∩ C| )
    #                      + ( |A ∩ B ∩ C| )
    #                      = |A U B U C |
    # By the inclusion excluion principle, which is what we wanted
    return cardinality_of_union


if __name__ == "__main__":
    import doctest

    doctest.testmod()
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  • reduce_w_cache

    • Prone to hitting recursion limits. You should use an iterative approach not a functional one.

      >>> reduce_w_cache(int.__add__, (1,) * 1000)
      Traceback (most recent call last):
        File "<stdin>", line 1, in <module>
        File "<stdin>", line 6, in reduce_w_cache
        File "<stdin>", line 6, in reduce_w_cache
        File "<stdin>", line 6, in reduce_w_cache
        [Previous line repeated 496 more times]
      RecursionError: maximum recursion depth exceeded
      
    • Doesn't work with a sequence of 0. Convention is to provide a default kwarg, eg; max, min, dict.get.

      >>> max([], default=0)
      0
      
    • Your function is slow \$O(n^2)\$ you can get an (amortized) \$O(n)\$ performance by building the cache yourself. A very basic and naive (aka broken) approach could be:

      1. Store the size of the cache. This prevents us from needing to slice the input (getting \$O(n^2)\$ time).

      2. Iteratively build the cache. Suppose we use reduce_w_cache to hash the sequence, you should notice we can just build off the previous hash.

      _hash = 0
      for size, value in enumerate(sequence, 1):
          _hash ^= hash(value)
          cache[size, _hash] = ...
      

      To make the algorithm work you would need to properly handle collisions (the hard part of building a hash map). You should store the original in the key, but not use it to compare values. If the size and hash match then you need to use it to compare collisions using an \$O(nk)\$ algorithm. Where \$n\$ is the size of the value and \$k\$ is the amount of collisions.

      To reduce collisions you'd have to take into account the birthday problem, and so can get a little memory hungry.

    Overall I think functools.reduce would be better here.

  • powerset
    About what I expect from a powerset function.

    • I think flatten is a bad design, and makes your function succeptable to becoming a god function.

      powerset(..., flatten=True)
      

      vs

      flatten = itertools.chain.from_iterable
      flatten(powerset(...))
      
    • "Input must be list or iterable" and isinstance(iterable, list) are odd as list is an iterable. You can probably just remove the code.

      >>> import collections.abc
      >>> issubclass(list, collections.abc.Iterable)
      True
      
  • IEP

    • Should be a Protocol.

    • IEP should be called IIEP, well anything other than IEP. The additional I is nomenculture taken from C# standing for "Interface".

      The biggest benefit, and why I've copied the style from C#, is not having duplicate names for the interface and the implementation.

  • ConstructorIEP Looks rather good. But have some nitpicks.

    • I don't like the dunder methods being at the bottom of your class. Regardless kudos are due for having a clear style.

      Here is my style:

      1. Type hints.

      2. Constructors.

        • __new__
        • __init__
        • Class or static builders.
      3. Dunder methods

      4. Everything else

      I class 'helper functions' to be grouped with the source function. Say you have a dunder method which is getting a bit big, splitting the function in two methos (one dunder one normal) shouldn't move the normal method to the bottom of the class.

    • intersection looks a little off.

      if len(others) == 0:
          new_structure = self.structure
      new_structure = self.structure
      
    • Your str dunder should call __len__ not lookup len. Makes your code more Pythonic and allows subclasses to follow Python's idioms and still have the code work fine.

  • make_IEP

    • I think the function should be a class builder on ConstructorIEP.

    • I'm not a fan of self.intersect = intersect. Bind the method to the class not the instance.

      @classmethod
      def build_type(cls, intersect: Intersection, cardinality: Cardinality) -> Type[IEP]:
          """Creates an IEP class with a fixed intersect and cardinality"""
      
          class IEP(ConstructorIEP):
              intersect = staticmethod(intersect)
              cardinality = staticmethod(cardinality)
      
              def __init__(self, structure: Structure):
                  self.structure = structure
      
          return IEP
      
  • inclusion_exclusion_principle (not a full review)

    • intersection_ should be intersection and intersection should be intersection_. A user of your function couldn't care less what the internal names of your function are, but do care about having sensible argument names.

    • Why have you defined IEP again and not used make_IEP?

    I'm no mathematician so I'm going to stop here.

Overall my answer is mostly nitpicks or somewhat trivial tidbits. Good code.

\$\endgroup\$
3
  • \$\begingroup\$ I never knew I could push the class builder into ConstructorIEP! =) Similarly staticmethod was the missing piece, I tried to bind the methods to the class and not the instance, but could not make it work. Why IEP was defined again was leftover code from a refactor attempt (wanted to remove make_IEP). \$\endgroup\$ Aug 15, 2021 at 8:09
  • \$\begingroup\$ As an after thought do I need the ConstructorIEP class? Or could I simply shove everything into the build_type function? It seems a little off that the IEP's inherit the build_type classmethod. \$\endgroup\$ Aug 15, 2021 at 8:11
  • \$\begingroup\$ @N3buchadnezzar I don't really see anything wrong with having ConstructorIEP which builds a new type. At the end of the day the builder is just a helper method. If your code becomes more complex then relying on a helper method for core functionality could be bad, but we'd need to know the situation to actually comment on whether the approach is sub-optimal. You could try other methods to do what you want, but if all the approaches work optimally, what's the problem? Regardless, I find meta programming to be quite abnormal and doesn't follow 'normal' processes. \$\endgroup\$
    – Peilonrayz
    Aug 15, 2021 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.