Skip to main content
`Ctrl`+`K`

# equivalence_classes

equivalence_classes(iterable, relation)

  Returns equivalence classes of `relation` when applied to `iterable`.

  The equivalence classes, or blocks, consist of objects from `iterable` which are all equivalent. They are defined to be equivalent if the `relation` function returns `True` when passed any two objects from that class, and `False` otherwise. To define an equivalence relation the function must be reflexive, symmetric and transitive.

  Parameters:
    iterable list, tuple, or set

      An iterable of elements/nodes.

    relation function

      A Boolean-valued function that implements an equivalence relation (reflexive, symmetric, transitive binary relation) on the elements of `iterable` - it must take two elements and return `True` if they are related, or `False` if not.

  Returns:
    set of frozensets

      A set of frozensets representing the partition induced by the equivalence relation function `relation` on the elements of `iterable`. Each member set in the return set represents an equivalence class, or block, of the partition.

      Duplicate elements will be ignored so it makes the most sense for `iterable` to be a `set`.

  Notes

  This function does not check that `relation` represents an equivalence relation. You can check that your equivalence classes provide a partition using `is_partition`.

  Examples

  Let `X` be the set of integers from `0` to `9`, and consider an equivalence relation `R` on `X` of congruence modulo `3`: this means that two integers `x` and `y` in `X` are equivalent under `R` if they leave the same remainder when divided by `3`, i.e. `(x - y) mod 3 = 0`.

  The equivalence classes of this relation are `{0, 3, 6, 9}`, `{1, 4, 7}`, `{2, 5, 8}`: `0`, `3`, `6`, `9` are all divisible by `3` and leave zero remainder; `1`, `4`, `7` leave remainder `1`; while `2`, `5` and `8` leave remainder `2`. We can see this by calling `equivalence_classes` with `X` and a function implementation of `R`.

      >>> X = set(range(10))
      >>> def mod3(x, y):
      ...     return (x - y) % 3 == 0
      >>> equivalence_classes(X, mod3)
      {frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}