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:

iterablelist, tuple, or set

An iterable of elements/nodes.

relationfunction

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})}