A simple brute-force algorithm to create equivalence classes of a collection based on an equivalence relation.

equivalence.py

def build_equivalence_classes(a_collection, comparer):
    """Given a collection of items that can be compared,
    and a comparer for those items, return a new collection
    of sublists that are equivalence classes of items in the
    original collection.

    """

    classes = []
    accounted_for = [False] * len(a_collection)

    for i in range(len(a_collection)):
        if accounted_for[i]:
            continue
        item = a_collection[i]
        equivalence_class = [item]
        for j in range(i + 1, len(a_collection)):
            if accounted_for[j]:
                continue
            other_item = a_collection[j]
            if comparer(item, other_item):
                equivalence_class.append(other_item)
                accounted_for[j] = True

        classes.append(equivalence_class)
        accounted_for[i] = True
    return classes


def n_ary_equiv(n):    
    """Given n, return a function that determines
    if two numbers belong to the same modulo class
    
    """
    
    def ary(a, b):
        if (a % n) == (b % n):
            return True
        else:
            return False
    return ary

if __name__ == "__main__":
    number_collection = range(1,10) # because who wants 0
    print(build_equivalence_classes(number_collection, n_ary_equiv(2)))
    print(build_equivalence_classes(number_collection, n_ary_equiv(3)))