equivalence_classes#
- equivalence_classes(iterable, relation)[source]#
Returns equivalence classes of
relation
when applied toiterable
.The equivalence classes, or blocks, consist of objects from
iterable
which are all equivalent. They are defined to be equivalent if therelation
function returnsTrue
when passed any two objects from that class, andFalse
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 returnTrue
if they are related, orFalse
if not.
- Returns:
- set of frozensets
A set of frozensets representing the partition induced by the equivalence relation function
relation
on the elements ofiterable
. 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 aset
.
Notes
This function does not check that
relation
represents an equivalence relation. You can check that your equivalence classes provide a partition usingis_partition
.Examples
Let
X
be the set of integers from0
to9
, and consider an equivalence relationR
onX
of congruence modulo3
: this means that two integersx
andy
inX
are equivalent underR
if they leave the same remainder when divided by3
, 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 by3
and leave zero remainder;1
,4
,7
leave remainder1
; while2
,5
and8
leave remainder2
. We can see this by callingequivalence_classes
withX
and a function implementation ofR
.>>> 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})}